yukicoder No.912 - 赤黒木

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20191102-1）のコード

C++に変換後のコードはこちら

int N, A[2d5], B[2d5], deg[2d5], cnv[2d5], rev[2d5];
int od[2d5], dp[3][2d5], nx[3];
{
  int res;
  graph g;
  rd(N,(A--,B--)(N-1));
  g.setEdgeRootedTree(N, N-1, A, B, 0, 1, cnv);
  rep(i,N) rev[cnv[i]] = i;
  rep(2N-2) deg[rev[rd_int()-1]] ^= 1;
  rep(i,1,3) rep(j,N) dp[i][j] = int_inf;
  rrep(i,N){
    od[i] = deg[i];
    rep[g.edge[i]](k,g.es[i]) od[i] ^= od[k];
    rep[g.edge[i]](k,g.es[i]){
      rep(x,3) nx[x] = int_inf;
      rep(x,3) rep(y,3) if(x+y <= 2){
        nx[x+y] <?= dp[x][i] + dp[y][k] + (od[k] + y) % 2;
      }
      if(deg[k]) rep(x,2) rep(y,2) if(x+y+1 <= 2){
        nx[x+y+1] <?= dp[x][i] + dp[y][k] + (od[k] + y + 1) % 2;
      }
      rep(x,3) dp[x][i] = nx[x];
    }
  }
  res = N - 1 + min(dp[0][0], dp[2][0]);
  if(deg[0]) res <?= N - 1 + dp[1][0];
  wt(res);
}

Current time: 2024年04月26日00時23分45秒
Last modified: 2019年11月02日11時41分16秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：