#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;
vector<ll> tree;
vector<int> pos;
vector<ll> lazy;
segtree(){}
void resize(int size){
n = size;
tree = vector<ll> (n*4,0);
pos = vector<int> (n*4,0);
lazy = vector<ll> (n*4,0);
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;
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(1);
temp = getfar(temp.second);
prevans = temp.first;
printf("%lld\n",prevans);
}
return 0;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:161: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:165: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:181: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 |
2808 KB |
Output is correct |
2 |
Correct |
7 ms |
2808 KB |
Output is correct |
3 |
Correct |
7 ms |
2808 KB |
Output is correct |
4 |
Correct |
7 ms |
2808 KB |
Output is correct |
5 |
Correct |
7 ms |
2808 KB |
Output is correct |
6 |
Correct |
6 ms |
2808 KB |
Output is correct |
7 |
Correct |
8 ms |
2936 KB |
Output is correct |
8 |
Correct |
7 ms |
2936 KB |
Output is correct |
9 |
Correct |
7 ms |
2936 KB |
Output is correct |
10 |
Correct |
7 ms |
2936 KB |
Output is correct |
11 |
Correct |
7 ms |
2936 KB |
Output is correct |
12 |
Correct |
7 ms |
2936 KB |
Output is correct |
13 |
Correct |
8 ms |
3064 KB |
Output is correct |
14 |
Correct |
7 ms |
3064 KB |
Output is correct |
15 |
Correct |
8 ms |
3064 KB |
Output is correct |
16 |
Correct |
7 ms |
3064 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2808 KB |
Output is correct |
2 |
Correct |
7 ms |
2808 KB |
Output is correct |
3 |
Correct |
7 ms |
2808 KB |
Output is correct |
4 |
Correct |
7 ms |
2808 KB |
Output is correct |
5 |
Correct |
7 ms |
2808 KB |
Output is correct |
6 |
Correct |
6 ms |
2808 KB |
Output is correct |
7 |
Correct |
8 ms |
2936 KB |
Output is correct |
8 |
Correct |
7 ms |
2936 KB |
Output is correct |
9 |
Correct |
7 ms |
2936 KB |
Output is correct |
10 |
Correct |
7 ms |
2936 KB |
Output is correct |
11 |
Correct |
7 ms |
2936 KB |
Output is correct |
12 |
Correct |
7 ms |
2936 KB |
Output is correct |
13 |
Correct |
8 ms |
3064 KB |
Output is correct |
14 |
Correct |
7 ms |
3064 KB |
Output is correct |
15 |
Correct |
8 ms |
3064 KB |
Output is correct |
16 |
Correct |
7 ms |
3064 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
19 |
Correct |
54 ms |
4728 KB |
Output is correct |
20 |
Correct |
60 ms |
4728 KB |
Output is correct |
21 |
Correct |
68 ms |
4728 KB |
Output is correct |
22 |
Correct |
70 ms |
4728 KB |
Output is correct |
23 |
Correct |
116 ms |
12024 KB |
Output is correct |
24 |
Correct |
122 ms |
12280 KB |
Output is correct |
25 |
Correct |
137 ms |
12536 KB |
Output is correct |
26 |
Correct |
154 ms |
12664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2808 KB |
Output is correct |
2 |
Correct |
6 ms |
2808 KB |
Output is correct |
3 |
Correct |
9 ms |
2808 KB |
Output is correct |
4 |
Correct |
25 ms |
2936 KB |
Output is correct |
5 |
Correct |
95 ms |
3192 KB |
Output is correct |
6 |
Correct |
7 ms |
2808 KB |
Output is correct |
7 |
Correct |
8 ms |
3576 KB |
Output is correct |
8 |
Correct |
8 ms |
3576 KB |
Output is correct |
9 |
Correct |
11 ms |
3576 KB |
Output is correct |
10 |
Correct |
39 ms |
3704 KB |
Output is correct |
11 |
Correct |
162 ms |
4088 KB |
Output is correct |
12 |
Correct |
17 ms |
11256 KB |
Output is correct |
13 |
Correct |
17 ms |
11256 KB |
Output is correct |
14 |
Correct |
21 ms |
11384 KB |
Output is correct |
15 |
Correct |
61 ms |
11384 KB |
Output is correct |
16 |
Correct |
229 ms |
11896 KB |
Output is correct |
17 |
Correct |
200 ms |
169704 KB |
Output is correct |
18 |
Correct |
191 ms |
169704 KB |
Output is correct |
19 |
Correct |
199 ms |
169832 KB |
Output is correct |
20 |
Correct |
259 ms |
169960 KB |
Output is correct |
21 |
Correct |
493 ms |
170472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4856 KB |
Output is correct |
2 |
Correct |
119 ms |
4728 KB |
Output is correct |
3 |
Correct |
565 ms |
4984 KB |
Output is correct |
4 |
Correct |
1153 ms |
5468 KB |
Output is correct |
5 |
Correct |
96 ms |
21496 KB |
Output is correct |
6 |
Correct |
259 ms |
21516 KB |
Output is correct |
7 |
Correct |
944 ms |
22008 KB |
Output is correct |
8 |
Correct |
1856 ms |
22116 KB |
Output is correct |
9 |
Correct |
473 ms |
96248 KB |
Output is correct |
10 |
Correct |
736 ms |
96248 KB |
Output is correct |
11 |
Correct |
2060 ms |
96792 KB |
Output is correct |
12 |
Correct |
3713 ms |
97084 KB |
Output is correct |
13 |
Correct |
1014 ms |
190840 KB |
Output is correct |
14 |
Correct |
1365 ms |
191248 KB |
Output is correct |
15 |
Correct |
2987 ms |
191256 KB |
Output is correct |
16 |
Correct |
4964 ms |
191600 KB |
Output is correct |
17 |
Execution timed out |
5072 ms |
191420 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5044 ms |
190744 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
2808 KB |
Output is correct |
2 |
Correct |
7 ms |
2808 KB |
Output is correct |
3 |
Correct |
7 ms |
2808 KB |
Output is correct |
4 |
Correct |
7 ms |
2808 KB |
Output is correct |
5 |
Correct |
7 ms |
2808 KB |
Output is correct |
6 |
Correct |
6 ms |
2808 KB |
Output is correct |
7 |
Correct |
8 ms |
2936 KB |
Output is correct |
8 |
Correct |
7 ms |
2936 KB |
Output is correct |
9 |
Correct |
7 ms |
2936 KB |
Output is correct |
10 |
Correct |
7 ms |
2936 KB |
Output is correct |
11 |
Correct |
7 ms |
2936 KB |
Output is correct |
12 |
Correct |
7 ms |
2936 KB |
Output is correct |
13 |
Correct |
8 ms |
3064 KB |
Output is correct |
14 |
Correct |
7 ms |
3064 KB |
Output is correct |
15 |
Correct |
8 ms |
3064 KB |
Output is correct |
16 |
Correct |
7 ms |
3064 KB |
Output is correct |
17 |
Correct |
7 ms |
3064 KB |
Output is correct |
18 |
Correct |
8 ms |
3064 KB |
Output is correct |
19 |
Correct |
54 ms |
4728 KB |
Output is correct |
20 |
Correct |
60 ms |
4728 KB |
Output is correct |
21 |
Correct |
68 ms |
4728 KB |
Output is correct |
22 |
Correct |
70 ms |
4728 KB |
Output is correct |
23 |
Correct |
116 ms |
12024 KB |
Output is correct |
24 |
Correct |
122 ms |
12280 KB |
Output is correct |
25 |
Correct |
137 ms |
12536 KB |
Output is correct |
26 |
Correct |
154 ms |
12664 KB |
Output is correct |
27 |
Correct |
7 ms |
2808 KB |
Output is correct |
28 |
Correct |
6 ms |
2808 KB |
Output is correct |
29 |
Correct |
9 ms |
2808 KB |
Output is correct |
30 |
Correct |
25 ms |
2936 KB |
Output is correct |
31 |
Correct |
95 ms |
3192 KB |
Output is correct |
32 |
Correct |
7 ms |
2808 KB |
Output is correct |
33 |
Correct |
8 ms |
3576 KB |
Output is correct |
34 |
Correct |
8 ms |
3576 KB |
Output is correct |
35 |
Correct |
11 ms |
3576 KB |
Output is correct |
36 |
Correct |
39 ms |
3704 KB |
Output is correct |
37 |
Correct |
162 ms |
4088 KB |
Output is correct |
38 |
Correct |
17 ms |
11256 KB |
Output is correct |
39 |
Correct |
17 ms |
11256 KB |
Output is correct |
40 |
Correct |
21 ms |
11384 KB |
Output is correct |
41 |
Correct |
61 ms |
11384 KB |
Output is correct |
42 |
Correct |
229 ms |
11896 KB |
Output is correct |
43 |
Correct |
200 ms |
169704 KB |
Output is correct |
44 |
Correct |
191 ms |
169704 KB |
Output is correct |
45 |
Correct |
199 ms |
169832 KB |
Output is correct |
46 |
Correct |
259 ms |
169960 KB |
Output is correct |
47 |
Correct |
493 ms |
170472 KB |
Output is correct |
48 |
Correct |
24 ms |
4856 KB |
Output is correct |
49 |
Correct |
119 ms |
4728 KB |
Output is correct |
50 |
Correct |
565 ms |
4984 KB |
Output is correct |
51 |
Correct |
1153 ms |
5468 KB |
Output is correct |
52 |
Correct |
96 ms |
21496 KB |
Output is correct |
53 |
Correct |
259 ms |
21516 KB |
Output is correct |
54 |
Correct |
944 ms |
22008 KB |
Output is correct |
55 |
Correct |
1856 ms |
22116 KB |
Output is correct |
56 |
Correct |
473 ms |
96248 KB |
Output is correct |
57 |
Correct |
736 ms |
96248 KB |
Output is correct |
58 |
Correct |
2060 ms |
96792 KB |
Output is correct |
59 |
Correct |
3713 ms |
97084 KB |
Output is correct |
60 |
Correct |
1014 ms |
190840 KB |
Output is correct |
61 |
Correct |
1365 ms |
191248 KB |
Output is correct |
62 |
Correct |
2987 ms |
191256 KB |
Output is correct |
63 |
Correct |
4964 ms |
191600 KB |
Output is correct |
64 |
Execution timed out |
5072 ms |
191420 KB |
Time limit exceeded |