AtCoder Beginner Contest #133
問題文
省略
省略
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日02時42分49秒
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)