#include "factories.h"
const int N_ = 500050;
int up[N_][19];
long long ul[N_][19];
int st[N_], en[N_<<1], len[N_<<1], nxt[N_<<1];
inline void addE(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
int chk[N_], down[N_];
void dfs_p(int x,int fa){
down[x] = 1;
for(int i=st[x];i;i=nxt[i])if(en[i] != fa && !chk[en[i]])dfs_p(en[i], x), down[x] += down[en[i]];
}
void dfs_l(int x,int fa,int cnt,int p){
for(int i=st[x];i;i=nxt[i])if(en[i] != fa && !chk[en[i]])up[en[i]][cnt] = p, ul[en[i]][cnt] = ul[x][cnt] + len[i], dfs_l(en[i], x, cnt, p);
}
void Decomp(int x, int depth){
int half = down[x] / 2;
for(;;){
int i;
for(i=st[x];i;i=nxt[i]){
if(!chk[en[i]] && down[en[i]] < down[x] && down[en[i]] > half)break;
}
if(!i)break;
x = en[i];
}
up[x][depth] = x;
dfs_l(x, -1, depth, x);
chk[x] = 1;
for(int i=st[x];i;i=nxt[i]){
if(chk[en[i]])continue;
dfs_p(en[i], -1);
Decomp(en[i], depth+1);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++)addE(A[i]+1, B[i]+1, D[i], i+i+1), addE(B[i]+1, A[i]+1, D[i], i+i+2);
dfs_p(1, -1);
Decomp(1, 0);
}
long long dis[N_][2];
int C;
void update(int p){
for(int i=0;up[p][i];i++){
int x = up[p][i];
if(dis[x][1] != C)dis[x][1] = C, dis[x][0] = ul[p][i];
else if(dis[x][0] > ul[p][i])dis[x][0] = ul[p][i];
}
}
long long read(int p){
long long ret = 5e13;
for(int i=0;up[p][i];i++){
int x = up[p][i];
if(dis[x][1] == C && ret > dis[x][0] + ul[p][i])ret = dis[x][0] + ul[p][i];
}
return ret;
}
long long Query(int S, int X[], int T, int Y[]) {
++C;
for(int i=0;i<S;i++)update(X[i]+1);
long long ans = 5e13;
for(int i=0;i<T;i++){
long long t = read(Y[i]+1);
if(ans > t)ans = t;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
160088 KB |
Output is correct |
2 |
Correct |
364 ms |
160088 KB |
Output is correct |
3 |
Correct |
396 ms |
160088 KB |
Output is correct |
4 |
Correct |
376 ms |
160088 KB |
Output is correct |
5 |
Correct |
400 ms |
160172 KB |
Output is correct |
6 |
Correct |
268 ms |
160088 KB |
Output is correct |
7 |
Correct |
396 ms |
160088 KB |
Output is correct |
8 |
Correct |
392 ms |
160088 KB |
Output is correct |
9 |
Correct |
400 ms |
160168 KB |
Output is correct |
10 |
Correct |
284 ms |
160088 KB |
Output is correct |
11 |
Correct |
396 ms |
160088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
160088 KB |
Output is correct |
2 |
Correct |
1972 ms |
160088 KB |
Output is correct |
3 |
Incorrect |
2988 ms |
162692 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2272 ms |
160088 KB |
Output is correct |
2 |
Correct |
2388 ms |
160088 KB |
Output is correct |
3 |
Incorrect |
3448 ms |
161948 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |