Kyoto University Programming Contest 2019 J問題 - Link-cut tworee

Source

Kyoto University Programming Contest 2019
問題文

問題概要

省略

解法

省略

cLayversion 20191102-1)のコード

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

int N, A[2d5], B[2d5], C[2d5];
int deg[2d5];
ll dp[2d5]; int sz;
{
  int lf = 0;
  ll res = 0;
  unionFind uf;
  rd(N);
  rd((A--,B--,C)(2N-2));
  rep(i,N-1) A[i+N-1] += N, B[i+N-1] += N;
  rep(i,2N-2) deg[A[i]]++, deg[B[i]]++;

  uf.malloc(2N+1);
  uf.init(2N+1);
  uf(0,N);
  rep(i,2N) if(deg[i]==1) lf++, uf(i,2N);

  rsortA(2N-2, C, A, B);
  rep(i,2N-2){
    if(uf(A[i]) == uf(B[i])) dp[sz++] = C[i], continue;
    uf(A[i],B[i]);
  }
  REP(i,lf/2) res += dp[sz-1-i];
  wt(res);
}

Current time: 2021年09月25日01時07分00秒
Last modified: 2019年11月02日12時05分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: