AtCoder Beginner Contest 036 D問題 - 塗り絵

Source

AtCoder Beginner Contest 036
問題文

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

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

int N, A[1d5], B[1d5];

mint dp[2][1d5];
int od[1d5], vis[1d5];
{
  int i, j, k, t;
  graph g;
  rd(N,(A--,B--)(N-1));
  g.setEdge(N,N-1,A,B);
  g.preorder(od);
  for(t=N-1;t>=0;t--){
    i = od[t];
    vis[i] = 1;
    dp[0][i] = dp[1][i] = 1;
    rep(j,g.es[i]){
      k = g.edge[i][j];
      if(vis[k]){
        dp[0][i] *= (dp[0][k] + dp[1][k]);
        dp[1][i] *= dp[0][k];
      }
    }
  }
  wt(dp[0][0] + dp[1][0]);
}

Current time: 2024年04月26日03時52分56秒
Last modified: 2019年09月21日11時55分57秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC036 ABC_D
トップページに戻る

Logged in as: unknown user (not login)