省略
省略
C++に変換後のコードはこちら
int N, K, A[2d5], B[2d5], C[2d5], Q, S, T;
wgraph<int> g;
HLD hld;
int ord[2d5], dep[2d5];
int up1[2d5][18], up2[2d5][18];
ll costHP[2d5][18];
ll getCostHP(int i, int s){
ll res = 0;
rep(k,18) if(s&1<<k){
if(up1[i][k]==-1) return ll_inf;
res += costHP[i][k];
i = up1[i][k];
}
return res;
}
pair<int,int> getCost(int i, int s){
int j, k;
pair<int,int> res = make_pair(0,0);
rrep(k,18){
if(up2[i][k]==-1) continue;
if(dep[up2[i][k]] >= dep[i]-s){
j = up2[i][k];
res.first += (1<<k);
s -= dep[i] - dep[j];
i = j;
}
}
res.second = getCostHP(i,s);
return res;
}
{
int i, j, k;
pair<int,int> c1, c2;
rd(N,K,(A--,B--,C)(N-1),Q);
g.setEdge(N,N-1,A,B,C);
hld.init(g.g);
g.g.preorder(ord);
rep[ord](i,N){
j = hld.up(i);
rep(k,18) up1[i][k] = up2[i][k] = -1;
if(j==-1) continue;
up1[i][0] = j;
rep(k,g.es[i]) if(g.edge[i][k]==j) costHP[i][0] = g.cost[i][k], break;
rep(k,1,18){
up1[i][k] = up1[up1[i][k-1]][k-1];
if(up1[i][k]==-1) break;
costHP[i][k] = costHP[i][k-1] + costHP[up1[i][k-1]][k-1];
}
}
rep[ord](i,N){
dep[i] = k = hld.depth(i);
j = bsearch_min[int,x,1,k+1](getCostHP(i,x) >= K);
up2[i][0] = hld.up(i,j);
rep(k,1,18){
if(up2[i][k-1]==-1) break;
up2[i][k] = up2[up2[i][k-1]][k-1];
}
}
rep(Q){
rd(S--,T--);
k = hld.lca(S,T);
c1 = getCost(S, dep[S]-dep[k]);
c2 = getCost(T, dep[T]-dep[k]);
wt(c1.first + c2.first + if[c1.second + c2.second >= K, 1, 0]);
}
}
Current time: 2024年04月27日12時45分52秒
Last modified: 2019年12月27日20時36分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)