AtCoder Beginner Contest #120 D問題 - Decayed Bridges

Source

AtCoder Beginner Contest #120
問題文

問題概要

省略

解法

省略

cLayversion 20190715-1)のコード

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

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

int sz[1d5];
ll res[1d5];
{
  int i, x, y;
  unionFind uf;

  rd(N,M,(A--,B--)(M));

  uf.malloc(N);
  uf.init(N);
  rep(i,N) sz[i] = 1;

  res[M-1] = (ll) N * (N-1) / 2;
  for(i=M-1;i;i--){
    res[i-1] = res[i];
    x = uf(A[i]);
    y = uf(B[i]);
    if(uf(x,y)){
      if(x != uf(x)) swap(x, y);
      res[i-1] -= (ll) sz[x] * sz[y];
      sz[x] += sz[y];
    }
  }

  wtLn(res(M));
}

Current time: 2021年09月18日05時18分15秒
Last modified: 2019年07月16日01時19分14秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC120 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: