2019年11月10日22時36分34秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

Codeforces Round #599 DIV1 B問題/DIV2 D問題 - 0-1 MST

Source

Codeforces Round #599 DIV1 B問題 (1000pt)
Codeforces Round #599 DIV2 D問題 (2000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20191110-1）のコード

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

//no-unlocked
int N, M, A[1d5], B[1d5];
int nn, ind[1d5];
int mat[1000][1000], cnt[1000];
int mm, a[5d5], b[5d5], c[5d5];
graph g, tn;
{
  int i, j, k, res = 0;
  unionFind uf;
  rd(N,M,(A--,B--)(M));
  g.setEdge(N,M,A,B);
  k = argmin(g.es(N));
  if(g.es[k]==N-1) wt(N-1), return 0;

  rep(i,N) ind[i] = 0;
  nn = 1;
  rep[g.edge[k]](i,g.es[k]) ind[i] = nn++;

  rep(i,nn) rep(j,nn) mat[i][j] = 0;
  rep(i,M){
    j = ind[A[i]];
    k = ind[B[i]];
    mat[j][k]++;
    mat[k][j]++;
  }
  rep(i,N) cnt[ind[i]]++;

  rep(i,nn) rep(j,i+1,nn){
    k = if[mat[i][j]==cnt[i]*cnt[j], 1, 0];
    arrInsert(mm, mm, a, i, b, j, c, k);
  }
  sortA(mm, c, a, b);

  uf.malloc(nn);
  uf.init(nn);

  rep(i,mm) if(uf(a[i],b[i])) res += c[i];
  wt(res);
}

Current time: 2024年04月20日09時18分42秒
Last modified: 2019年11月10日22時36分34秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF599 CF_Div1_B CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)