AtCoder Beginner Contest #133 F問題 - Colorful Tree

Source

AtCoder Beginner Contest #133
問題文

問題概要

省略

解法

省略

cLay（version 20190708-1）のコード

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

int N, Q, A[1d5], B[1d5], C[1d5], D[1d5], X[1d5], Y[1d5], U[1d5], V[1d5];

int ind[1d5], val[1d5];
int up[1d5], cnv[1d5];
ll res[1d5];

graph g;
HLD hld;
HLD_fenwick<ll> t;

{
  int i, j, k, ii, c;
  ll r;
  
  rd(N,Q,(A--,B--,C,D)(N-1),(X,Y,U--,V--)(Q));

  sortA(N-1, C, A, B, D);
  
  rep(i,Q) val[i] = X[i];
  rep(i,Q) ind[i] = i;
  sortA(Q, val, ind);

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

  rep(i,N) up[i] = hld.up(i);
  rep(i,N-1) cnv[i] = if[ up[A[i]]==B[i], A[i], B[i] ];
  rep(i,N-1) t.add(cnv[i], D[i]);

  j = k = 0;
  rep(ii,Q){
    i = ind[ii];

    while(j < N-1 && C[j] <= X[i]){
      t.add(cnv[j], 1d10 - D[j]);
      j++;
    }
    while(k < N-1 && C[k] < X[i]){
      t.add(cnv[k], D[k] - 1d10);
      k++;
    }

    c = hld.lca(U[i], V[i]);
    r = t.get(U[i], V[i]) - t.get(c,c);
    res[i] = (r%1d10) + (r/1d10) * Y[i];
  }

  rep(i,Q) wt(res[i]);
}

Current time: 2024年04月27日03時29分31秒
Last modified: 2019年07月08日23時20分22秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC133 ABC_F
トップページに戻る

Logged in as: unknown user (not login)