yukicoder No.898 - tri-βutree

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20191006-1）のコード

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

int N, A[1d5], B[1d5], C[1d5];
int sz, X[1d5];
int dis[1d5], pre[1d5], val[1d5];

int nx[1d5], bf[1d5];

{
  int i, j, k, m;
  ll res;
  graph g;
  HLD hld;
  HLD_fenwick<ll> t;
  LHeap<int> hp;

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

  g.setEdge(N,N-1,A,B);
  hld.init(g);
  t.init(&hld);
  hp.walloc(N);

  g.getDist(0,dis);
  rep(i,N-1) if(dis[A[i]] > dis[B[i]]) swap(A[i], B[i]);
  rep(i,N-1) t.add(B[i], C[i]);

  g.preorder(val);
  rep(i,N) pre[val[i]] = i;

  REP(rd_int()){
    sz = 3;
    rd(X(sz));
    rep(i,sz) val[i] = pre[X[i]];
    sortA(sz, val, X);
    hp.init(sz-1);
    rep(i,sz-1){
      k = hld.lca(X[i],X[i+1]);
      hp.change(i, -dis[k]);
    }
    rep(i,sz) bf[i] = i-1;
    rep(i,sz) nx[i] = i+1;
    res = 0;
    rep(sz-1){
      i = hp.pop();
      j = nx[i];
      k = hld.lca(X[i], X[j]);
      res += t.get(X[i], k) - t.get(k,k);
      res += t.get(X[j], k) - t.get(k,k);
      X[j] = k;
      k = bf[j] = bf[i];
      if(k >= 0) nx[k] = j;
      if(0 <= j < sz-1 && 0 <= nx[j] < sz){
        m = hld.lca(X[j], X[nx[j]]);
        hp.change(j, -dis[m]);
      }
      if(0 <= k < sz-1 && 0 <= nx[k] < sz){
        m = hld.lca(X[k], X[nx[k]]);
        hp.change(k, -dis[m]);
      }
    }
    wt(res);
  }
}

Current time: 2024年04月26日09時34分09秒
Last modified: 2019年10月06日04時51分25秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)