Codeforces Round #572 DIV1 A2問題/DIV2 D2問題 - Add on a Tree: Revolution

Source

Codeforces Round #572 DIV1 A2問題 (750pt)
Codeforces Round #572 DIV2 D2問題 (1250pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20190706-1)のコード

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年03月19日17時17分20秒
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)

ログイン: