AtCoder Grand Contest 038 D問題 - Unique Path

Source

AtCoder Grand Contest 038
問題文

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

C++に変換後のコードはこちら

int N, Q, A[1d5], B[1d5], C[1d5];
ll M;
int ind[1d5];
{
  int i, j, k;
  unionFind uf;
  rd(N,M,Q,(A,B,C)(Q));

  if(M==N-1) rep(i,N) if(C[i]==1) wt("No"), return 0;

  uf.malloc(N);
  uf.init(N);

  rep(i,Q) if(C[i]==0) uf(A[i],B[i]);
  rep(i,Q) if(C[i]==1) if(uf(A[i]) == uf(B[i])) wt("No"), return 0;

  k = 0;
  rep(i,N){
    j = uf(i);
    if(!ind[j]) k++, ind[j]++;
  }

  M -= N - k;
  M -= (ll) k * (k-1) / 2;
  
  wt(if[M<=0, "Yes", "No"]);
}

Current time: 2024年04月20日19時59分22秒
Last modified: 2019年09月22日00時26分02秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC038 AGC_D
トップページに戻る

Logged in as: unknown user (not login)