第二回 アルゴリズム実技検定 O問題 - 可変全域木

Source

第二回 アルゴリズム実技検定
問題文

問題概要

省略

解法

省略

cLay（version 20201229-1）のコード

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

int N, M, A[1d5], B[1d5], C[1d5], ind[1d5];
ll res[1d5];

wgraph<int> g;
HLD hld;
HLD_segtree<int> t;

int mm, aa[1d5], bb[1d5], cc[1d5];
int val[1d5];

{
  int i, x;
  unionFind uf;
  ll bas = 0;

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

  rep(i,M) ind[i] = i;
  sortA(M,C,A,B,ind);

  uf.walloc(N, 1);
  rep(i,M) if(uf(A[i],B[i])){
    arrInsert(mm, mm, aa, A[i], bb, B[i], cc, C[i]);
    bas += C[i];
  }

  g.setEdge(N, mm, aa, bb, cc);
  hld.init(g.g);
  rep(i,mm){
    x = if[hld.depth(aa[i]) > hld.depth(bb[i]), aa[i], bb[i]];
    val[x] = -cc[i];
  }
  t.init(&hld, val);
  rep(i,M) res[ind[i]] = bas + C[i] + t.getMinVal_edge(A[i], B[i]);
  wtLn(res(M));
}

Current time: 2024年04月20日05時34分19秒
Last modified: 2021年01月02日17時04分59秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：