#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pl;
const int MAXN = 101010;
struct segtree{
int n;
ll tree[MAXN * 4];
int pos[MAXN * 4];
ll lazy[MAXN * 4];
segtree(){}
void resize(int size){
n = size;
init(1,1,n);
}
void init(int node,int s,int e){
if(s == e){
pos[node] = s;
return;
}
int m = (s + e) >> 1;
init(node<<1,s,m);
init(node<<1|1,m+1,e);
upnode(node);
}
void upnode(int node){
if(tree[node<<1] >= tree[node<<1|1]){
tree[node] = tree[node<<1];
pos[node] = pos[node<<1];
}
else{
tree[node] = tree[node<<1|1];
pos[node] = pos[node<<1|1];
}
}
void laz(int node,int s,int e){
if(s != e){
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
tree[node] += lazy[node];
lazy[node] = 0;
}
void update(int node,int s,int e,int l,int r,ll diff){
laz(node,s,e);
if(e < l||r < s) return;
if(l <= s && e <= r){
lazy[node] += diff;
laz(node,s,e);
return ;
}
int m = (s + e) >> 1;
update(node<<1,s,m,l,r,diff);
update(node<<1|1,m+1,e,l,r,diff);
upnode(node);
}
void update(int l,int r,ll diff){
update(1,1,n,l,r,diff);
}
pl range(int node,int s,int e,int l,int r){
laz(node,s,e);
if(e < l||r < s) return pl(0,0);
if(l <= s && e <= r) return pl(tree[node],pos[node]);
int m = (s + e) >> 1;
return max(range(node<<1,s,m,l,r) , range(node<<1 | 1 ,m+1,e,l,r));
}
pl range(int l,int r){
return range(1,1,n,l,r);
}
};
int N,Q;
ll W;
ll prevans = 0;
int siz[MAXN];
int prtedge[20][MAXN];
int cprt[MAXN];
int dep[MAXN];
vector<pl> edge[MAXN];
int vis[MAXN];
int cprtnode[MAXN];
int s[20][MAXN];
int e[20][MAXN];
int rdfn[20][MAXN];
int t[20];
ll elen[MAXN];
segtree myseg[20];
int szdfs(int node,int par){
siz[node] = 1;
for(auto i : edge[node]) if(i.first != par && !vis[i.first]) siz[node] += szdfs(i.first,node);
return siz[node];
}
int cdfs(int node,int par,int cap){
for(auto i : edge[node]) if(i.first != par && !vis[i.first] && siz[i.first] > cap) return cdfs(i.first,node,cap);
return node;
}
int dfs(int node,int par,int d){
e[d][node] = s[d][node] = ++t[d];
rdfn[d][s[d][node]] = node;
for(auto i : edge[node]){
if(i.first == par|| vis[i.first]) continue;
prtedge[d][i.second] = i.first;
e[d][node] = dfs(i.first,node,d);
}
// printf("%d %d %d %d\n",node,d,s[d][node],e[d][node]);
return e[d][node];
}
int decomp(int node,int par){
int cap = szdfs(node,par);
int cen = cdfs(node,par,cap/2);
cprt[cen] = par;
dep[cen] = dep[par] + 1;
dfs(cen,par,dep[cen]);
vis[cen] = 1;
for(auto i : edge[cen]){
if(i.first == par || vis[i.first]) continue;
int tcen = decomp(i.first,cen);
cprtnode[tcen] = i.first;
}
assert(dep[cen] < 20);
// printf("ang %d %d\n",cen,par);
return cen;
}
pl getfar(int node){
pl ret = pl(0,0);
int now = node;
int prv = -1;
while(now != 0){
pl temp = pl(0,0);
if(prv != -1){
int tprv = cprtnode[prv];
temp = max(temp , myseg[dep[now]].range(s[dep[now]][now] , s[dep[now]][tprv] - 1));
temp = max(temp , myseg[dep[now]].range(e[dep[now]][tprv] + 1 , e[dep[now]][now]));
}
else temp = myseg[dep[now]].range(s[dep[now]][now],e[dep[now]][now]);
temp.second = rdfn[dep[now]][temp.second];
temp.first += myseg[dep[now]].range(s[dep[now]][node],s[dep[now]][node]).first;
//printf("%d %d %lld %lld\n",node,now,temp.first,temp.second);
ret = max(temp,ret);
prv = now;
now = cprt[now];
}
return ret;
}
int main(){
scanf("%d %d %lld",&N,&Q,&W);
for(int i=0;i<20;i++) myseg[i].resize(N);
for(int i=0;i<N-1;i++){
int a,b;
scanf("%d %d %lld",&a,&b,&elen[i]);
edge[a].push_back(pl(b,i));
edge[b].push_back(pl(a,i));
}
dep[0] = -1;
int allcen = decomp(1,0);
for(int i=0;i<N-1;i++){
for(int j=0;j<20;j++){
if(!prtedge[j][i]) continue;
//printf("prtedge %d %d %d\n",j,i,prtedge[j][i]);
myseg[j].update(s[j][prtedge[j][i]] , e[j][prtedge[j][i]] , elen[i]);
}
}
for(int i=0;i<Q;i++){
int d;
ll E;
scanf("%d %lld",&d,&E);
d = (0LL + d + prevans) % (N - 1);
E = (E + prevans) % W;
//printf("query %d %lld\n",d,E);
for(int j=0;j<20;j++){
if(!prtedge[j][d]) continue;
// printf("updating %d %d %d\n",j, s[j][prtedge[j][d]] , e[j][prtedge[j][d]] );
myseg[j].update(s[j][prtedge[j][d]] , e[j][prtedge[j][d]] , E - elen[d]);
}
elen[d] = E;
pl temp = getfar(allcen);
temp = getfar(temp.second);
prevans = temp.first;
printf("%lld\n",prevans);
}
return 0;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&N,&Q,&W);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&a,&b,&elen[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %lld",&d,&E);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3192 KB |
Output is correct |
3 |
Correct |
7 ms |
3192 KB |
Output is correct |
4 |
Correct |
8 ms |
3168 KB |
Output is correct |
5 |
Correct |
7 ms |
3192 KB |
Output is correct |
6 |
Correct |
7 ms |
3192 KB |
Output is correct |
7 |
Correct |
8 ms |
3192 KB |
Output is correct |
8 |
Correct |
7 ms |
3192 KB |
Output is correct |
9 |
Correct |
8 ms |
3280 KB |
Output is correct |
10 |
Correct |
8 ms |
3320 KB |
Output is correct |
11 |
Correct |
8 ms |
3324 KB |
Output is correct |
12 |
Correct |
7 ms |
3196 KB |
Output is correct |
13 |
Correct |
8 ms |
3320 KB |
Output is correct |
14 |
Correct |
8 ms |
3320 KB |
Output is correct |
15 |
Correct |
8 ms |
3320 KB |
Output is correct |
16 |
Correct |
8 ms |
3320 KB |
Output is correct |
17 |
Correct |
8 ms |
3320 KB |
Output is correct |
18 |
Correct |
8 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3192 KB |
Output is correct |
3 |
Correct |
7 ms |
3192 KB |
Output is correct |
4 |
Correct |
8 ms |
3168 KB |
Output is correct |
5 |
Correct |
7 ms |
3192 KB |
Output is correct |
6 |
Correct |
7 ms |
3192 KB |
Output is correct |
7 |
Correct |
8 ms |
3192 KB |
Output is correct |
8 |
Correct |
7 ms |
3192 KB |
Output is correct |
9 |
Correct |
8 ms |
3280 KB |
Output is correct |
10 |
Correct |
8 ms |
3320 KB |
Output is correct |
11 |
Correct |
8 ms |
3324 KB |
Output is correct |
12 |
Correct |
7 ms |
3196 KB |
Output is correct |
13 |
Correct |
8 ms |
3320 KB |
Output is correct |
14 |
Correct |
8 ms |
3320 KB |
Output is correct |
15 |
Correct |
8 ms |
3320 KB |
Output is correct |
16 |
Correct |
8 ms |
3320 KB |
Output is correct |
17 |
Correct |
8 ms |
3320 KB |
Output is correct |
18 |
Correct |
8 ms |
3320 KB |
Output is correct |
19 |
Correct |
36 ms |
4088 KB |
Output is correct |
20 |
Correct |
41 ms |
4088 KB |
Output is correct |
21 |
Correct |
44 ms |
4128 KB |
Output is correct |
22 |
Correct |
44 ms |
4216 KB |
Output is correct |
23 |
Correct |
82 ms |
8468 KB |
Output is correct |
24 |
Correct |
101 ms |
8952 KB |
Output is correct |
25 |
Correct |
116 ms |
9464 KB |
Output is correct |
26 |
Correct |
122 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3192 KB |
Output is correct |
2 |
Correct |
7 ms |
3064 KB |
Output is correct |
3 |
Correct |
9 ms |
3064 KB |
Output is correct |
4 |
Correct |
26 ms |
3192 KB |
Output is correct |
5 |
Correct |
111 ms |
3704 KB |
Output is correct |
6 |
Correct |
7 ms |
3068 KB |
Output is correct |
7 |
Correct |
8 ms |
3320 KB |
Output is correct |
8 |
Correct |
8 ms |
3320 KB |
Output is correct |
9 |
Correct |
11 ms |
3320 KB |
Output is correct |
10 |
Correct |
37 ms |
3448 KB |
Output is correct |
11 |
Correct |
158 ms |
3832 KB |
Output is correct |
12 |
Correct |
13 ms |
6520 KB |
Output is correct |
13 |
Correct |
13 ms |
6556 KB |
Output is correct |
14 |
Correct |
17 ms |
6648 KB |
Output is correct |
15 |
Correct |
53 ms |
6648 KB |
Output is correct |
16 |
Correct |
230 ms |
7160 KB |
Output is correct |
17 |
Correct |
120 ms |
57560 KB |
Output is correct |
18 |
Correct |
118 ms |
58320 KB |
Output is correct |
19 |
Correct |
147 ms |
60212 KB |
Output is correct |
20 |
Correct |
188 ms |
60664 KB |
Output is correct |
21 |
Correct |
395 ms |
60940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
4088 KB |
Output is correct |
2 |
Correct |
70 ms |
4088 KB |
Output is correct |
3 |
Correct |
326 ms |
4372 KB |
Output is correct |
4 |
Correct |
654 ms |
4664 KB |
Output is correct |
5 |
Correct |
71 ms |
15480 KB |
Output is correct |
6 |
Correct |
194 ms |
15640 KB |
Output is correct |
7 |
Correct |
764 ms |
15864 KB |
Output is correct |
8 |
Correct |
1480 ms |
16248 KB |
Output is correct |
9 |
Correct |
344 ms |
59896 KB |
Output is correct |
10 |
Correct |
571 ms |
60152 KB |
Output is correct |
11 |
Correct |
1594 ms |
60324 KB |
Output is correct |
12 |
Correct |
2781 ms |
60580 KB |
Output is correct |
13 |
Correct |
745 ms |
120568 KB |
Output is correct |
14 |
Correct |
1048 ms |
121080 KB |
Output is correct |
15 |
Correct |
2367 ms |
121428 KB |
Output is correct |
16 |
Correct |
3800 ms |
121656 KB |
Output is correct |
17 |
Correct |
4402 ms |
120316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4902 ms |
109772 KB |
Output is correct |
2 |
Execution timed out |
5035 ms |
115320 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3192 KB |
Output is correct |
2 |
Correct |
6 ms |
3192 KB |
Output is correct |
3 |
Correct |
7 ms |
3192 KB |
Output is correct |
4 |
Correct |
8 ms |
3168 KB |
Output is correct |
5 |
Correct |
7 ms |
3192 KB |
Output is correct |
6 |
Correct |
7 ms |
3192 KB |
Output is correct |
7 |
Correct |
8 ms |
3192 KB |
Output is correct |
8 |
Correct |
7 ms |
3192 KB |
Output is correct |
9 |
Correct |
8 ms |
3280 KB |
Output is correct |
10 |
Correct |
8 ms |
3320 KB |
Output is correct |
11 |
Correct |
8 ms |
3324 KB |
Output is correct |
12 |
Correct |
7 ms |
3196 KB |
Output is correct |
13 |
Correct |
8 ms |
3320 KB |
Output is correct |
14 |
Correct |
8 ms |
3320 KB |
Output is correct |
15 |
Correct |
8 ms |
3320 KB |
Output is correct |
16 |
Correct |
8 ms |
3320 KB |
Output is correct |
17 |
Correct |
8 ms |
3320 KB |
Output is correct |
18 |
Correct |
8 ms |
3320 KB |
Output is correct |
19 |
Correct |
36 ms |
4088 KB |
Output is correct |
20 |
Correct |
41 ms |
4088 KB |
Output is correct |
21 |
Correct |
44 ms |
4128 KB |
Output is correct |
22 |
Correct |
44 ms |
4216 KB |
Output is correct |
23 |
Correct |
82 ms |
8468 KB |
Output is correct |
24 |
Correct |
101 ms |
8952 KB |
Output is correct |
25 |
Correct |
116 ms |
9464 KB |
Output is correct |
26 |
Correct |
122 ms |
9848 KB |
Output is correct |
27 |
Correct |
7 ms |
3192 KB |
Output is correct |
28 |
Correct |
7 ms |
3064 KB |
Output is correct |
29 |
Correct |
9 ms |
3064 KB |
Output is correct |
30 |
Correct |
26 ms |
3192 KB |
Output is correct |
31 |
Correct |
111 ms |
3704 KB |
Output is correct |
32 |
Correct |
7 ms |
3068 KB |
Output is correct |
33 |
Correct |
8 ms |
3320 KB |
Output is correct |
34 |
Correct |
8 ms |
3320 KB |
Output is correct |
35 |
Correct |
11 ms |
3320 KB |
Output is correct |
36 |
Correct |
37 ms |
3448 KB |
Output is correct |
37 |
Correct |
158 ms |
3832 KB |
Output is correct |
38 |
Correct |
13 ms |
6520 KB |
Output is correct |
39 |
Correct |
13 ms |
6556 KB |
Output is correct |
40 |
Correct |
17 ms |
6648 KB |
Output is correct |
41 |
Correct |
53 ms |
6648 KB |
Output is correct |
42 |
Correct |
230 ms |
7160 KB |
Output is correct |
43 |
Correct |
120 ms |
57560 KB |
Output is correct |
44 |
Correct |
118 ms |
58320 KB |
Output is correct |
45 |
Correct |
147 ms |
60212 KB |
Output is correct |
46 |
Correct |
188 ms |
60664 KB |
Output is correct |
47 |
Correct |
395 ms |
60940 KB |
Output is correct |
48 |
Correct |
16 ms |
4088 KB |
Output is correct |
49 |
Correct |
70 ms |
4088 KB |
Output is correct |
50 |
Correct |
326 ms |
4372 KB |
Output is correct |
51 |
Correct |
654 ms |
4664 KB |
Output is correct |
52 |
Correct |
71 ms |
15480 KB |
Output is correct |
53 |
Correct |
194 ms |
15640 KB |
Output is correct |
54 |
Correct |
764 ms |
15864 KB |
Output is correct |
55 |
Correct |
1480 ms |
16248 KB |
Output is correct |
56 |
Correct |
344 ms |
59896 KB |
Output is correct |
57 |
Correct |
571 ms |
60152 KB |
Output is correct |
58 |
Correct |
1594 ms |
60324 KB |
Output is correct |
59 |
Correct |
2781 ms |
60580 KB |
Output is correct |
60 |
Correct |
745 ms |
120568 KB |
Output is correct |
61 |
Correct |
1048 ms |
121080 KB |
Output is correct |
62 |
Correct |
2367 ms |
121428 KB |
Output is correct |
63 |
Correct |
3800 ms |
121656 KB |
Output is correct |
64 |
Correct |
4402 ms |
120316 KB |
Output is correct |
65 |
Correct |
4902 ms |
109772 KB |
Output is correct |
66 |
Execution timed out |
5035 ms |
115320 KB |
Time limit exceeded |
67 |
Halted |
0 ms |
0 KB |
- |