2019年07月06日11時53分16秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Codeforces Round #572 DIV1 A2問題 (750pt)
Codeforces Round #572 DIV2 D2問題 (1250pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, A[1000], B[1000], C[1000][1000];
graph g;
int path[1000], ps;
int ress, resA[1d5], resB[1d5], resC[1d5];
void doit(int x, int y, int z){
int i;
ps = g.shortestPath(x, y, path);
rep(i,ps){
C[path[i]][path[i+1]] -= z;
C[path[i+1]][path[i]] -= z;
}
resA[ress] = x + 1;
resB[ress] = y + 1;
resC[ress++] = z;
}
void solve(int n, int r, int b, int &x, int &y){
int i, j, k;
int sx, sy;
rep(i, g.es[n]){
k = g.edge[n][i];
if(k==b) continue;
sx = sy = -1;
solve(k, r, n, sx, sy);
if(x==-1) x = sx;
else if(y==-1) y = sx;
}
if(b>=0 && C[n][b]){
k = C[n][b];
if(x >= 0 && y >= 0){
doit(x, y, -k/2);
doit(r, x, k/2);
doit(r, y, k/2);
} else if(g.es[n]==1) {
doit(n, r, k);
}
}
if(g.es[n]==1) x = n;
}
{
int i, j, k, m, rt;
rd(N);
rep(m,N-1){
rd(i--,j--,k);
A[m] = i;
B[m] = j;
C[i][j] = C[j][i] = k;
}
g.setEdge(N,N-1,A,B);
rep(i,N) if(g.es[i]==1) { rt = i; break; }
i = j = -1;
solve(rt, rt, -1, i, j);
k = 0;
rep(i,N) rep(j,N) if(C[i][j]) k++;
if(k){
wt("NO");
} else {
wt("YES");
wt(ress);
rep(i,ress) wt(resA[i], resB[i], resC[i]);
}
}
Current time: 2024年05月03日06時07分57秒
Last modified: 2019年07月06日11時53分16秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF572 CF_Div1_A CF_Div2_D
トップページに戻る
Logged in as: unknown user (not login)