Codeforces Round #599 DIV1 B問題 (1000pt)
Codeforces Round #599 DIV2 D問題 (2000pt)
Problem description
省略
省略
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日20時29分09秒
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)