2019年11月02日12時05分31秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Kyoto University Programming Contest 2019
問題文
省略
省略
C++に変換後のコードはこちら
int N, A[2d5], B[2d5], C[2d5];
int deg[2d5];
ll dp[2d5]; int sz;
{
int lf = 0;
ll res = 0;
unionFind uf;
rd(N);
rd((A--,B--,C)(2N-2));
rep(i,N-1) A[i+N-1] += N, B[i+N-1] += N;
rep(i,2N-2) deg[A[i]]++, deg[B[i]]++;
uf.malloc(2N+1);
uf.init(2N+1);
uf(0,N);
rep(i,2N) if(deg[i]==1) lf++, uf(i,2N);
rsortA(2N-2, C, A, B);
rep(i,2N-2){
if(uf(A[i]) == uf(B[i])) dp[sz++] = C[i], continue;
uf(A[i],B[i]);
}
REP(i,lf/2) res += dp[sz-1-i];
wt(res);
}
Current time: 2024年05月03日05時44分06秒
Last modified: 2019年11月02日12時05分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)