Codeforces Round #586 E問題 - Tourism

Source

Codeforces Round #586 E問題 (2750pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

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

//no-unlocked
int N, M, W[2d5], A[2d5], B[2d5], S;

int nn, grp[2d5], vis[2d5], od[2d5];
ll dp1[2d5], dp2[2d5];
ll ww[2d5]; int sz[2d5];
{
  int i, j, k, d;
  ll s;
  graph og, g;
  rd(N,M,W(N),(A--,B--)(M),S--);

  og.setEdge(N,M,A,B);
  nn = og.bcc(grp);
  g = og.reduce(nn, grp);
  rep(i,N) ww[grp[i]] += W[i];
  rep(i,N) sz[grp[i]]++;
  S = grp[S];
  g.preorder(od, S);
  rrep(k,nn){
    i = od[k];
    s = ww[i];
    vis[i] = 1;
    rep(j,g.es[i]){
      d = g.edge[i][j];
      if(!vis[d]) continue;
      if(sz[d] >= 2){
        sz[i] += sz[d];
        s += dp2[d];
      }
    }
    dp1[i] = dp2[i] = s;
    rep(j,g.es[i]){
      d = g.edge[i][j];
      if(sz[d] >= 2) dp1[i] >?= dp1[d] + s - dp2[d];
      else           dp1[i] >?= dp1[d] + s;
    }
  }
  wt(dp1[S]);
}

Current time: 2024年04月26日01時36分40秒
Last modified: 2019年09月21日12時32分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF586
トップページに戻る

Logged in as: unknown user (not login)