AtCoder Regular Contest 108 C問題 - Keep Graph Connected

Source

AtCoder Regular Contest 108
問題文

問題概要

省略

解法

省略

cLay（version 20201121-1）のコード

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

int N, M, A[2d5], B[2d5], C[2d5];
graph g;
int res[2d5], d[2d5], up[2d5], ord[2d5], m;
{
  int i, k = 0;
  unionFind uf;
  rd(N,M,(A--,B--,C--)(M));
  uf.walloc(N,1);
  rep(i,M) if(uf(A[i],B[i])) arrInsert(k, k, A, A[i], B, B[i], C, C[i]);
  g.setEdge(N, N-1, A, B);
  g.getDist(0, d);
  rep(i,N-1){
    if(d[A[i]] > d[B[i]]) swap(A[i], B[i]);
    up[B[i]] = A[i];
    res[B[i]] = C[i];
  }
  g.preorder(ord);
  rep[ord](i,1,N) if(res[i]==res[up[i]]) res[i] = (res[i]+1)%N;
  wtLn(res(N)+1);
}

Current time: 2024年04月26日23時39分14秒
Last modified: 2020年11月22日17時04分32秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Regular_Contest ARC108 ARC_C
トップページに戻る

Logged in as: unknown user (not login)