AtCoder Grand Contest #034 E問題 - Complete Compress

Source

AtCoder Grand Contest #034
問題文

問題概要

省略

解法

省略

cLayversion 20190601-1)のコード

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: 2021年09月28日23時17分49秒
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)

ログイン: