AtCoder Grand Contest #034
問題文
省略
省略
C++に変換後のコードはこちら
int N;
char S[2002];
int A[2000], B[2000];
graph g;
int cnt[2000], mn[2000], mx[2000];
void dfs(int n, int b){
int i, k, t;
rep(i, g.es[n]){
k = g.edge[n][i];
if(k==b) continue;
dfs(k, n);
}
cnt[n] = mx[n] = 0;
rep(i, g.es[n]){
k = g.edge[n][i];
if(k==b) continue;
cnt[n] += cnt[k];
mx[n] += mx[k] + cnt[k];
}
mn[n] = 0;
rep(i, g.es[n]){
k = g.edge[n][i];
if(k==b) continue;
t = (mn[k]+cnt[k]) - mx[n] + (mx[k]+cnt[k]);
if(t < 0) t = (t + 1d9) % 2;
mn[n] >?= t;
}
if(S[n]=='1') cnt[n]++;
}
{
int i, j, k, n, s;
int res;
rd(N,S,(A,B)(N-1));
rep(i,N-1) A[i]--;
rep(i,N-1) B[i]--;
g.setEdge(N, N-1, A, B);
res = int_inf;
rep(n,N){
dfs(n, -1);
if(mn[n]==0) res <?= mx[n]/2;
}
if(res==int_inf) res = -1;
wt(res);
}
Current time: 2024年03月29日20時54分39秒
Last modified: 2019年06月03日00時05分48秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC034 AGC_E
トップページに戻る
Logged in as: unknown user (not login)