Codeforces Round #582 DIV3 G問題 - Path Queries

Source

Codeforces Round #582 DIV3 G問題
Problem description

問題概要

省略

解法

省略

cLay（version 20190830-1）のコード

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

//no-unlocked
int N, T, A[2d5], B[2d5], C[2d5], Q[2d5];
int ind[2d5], sz[2d5];
ll res[2d5];
{
  int i, j, k, m, t;
  ll tmp = 0;
  unionFind uf;

  rd(N,T,(A--,B--,C)(N-1),Q(T));
  sortA(N-1, C, A, B);
  rep(i,T) ind[i] = i;
  sortA(T, Q, ind);

  uf.walloc(N);
  uf.init(N);

  rep(i,N) sz[i] = 1;
  m = 0;
  rep(t,T){
    while(m < N-1 && C[m] <= Q[t]){
      i = uf(A[m]);
      j = uf(B[m]);
      m++;
      if(i==j) continue;
      uf(i,j);
      k = uf(i);

      tmp += (ll)sz[i] * sz[j];
      sz[k] = sz[i] + sz[j];
    }
    res[ind[t]] = tmp;
  }

  wt(res(T));
}

Current time: 2024年04月20日06時47分23秒
Last modified: 2019年09月01日00時52分22秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF582 CF_Div3_G
トップページに戻る

Logged in as: unknown user (not login)