#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
const long long inf = (1LL << 60LL);
typedef pair<long long, long long> ii;
struct edge { long long u, v, w; vector<int> trees; vector<ii> preorder; };
struct segment{
int n;
vector<ii> tree;
vector<long long> lazy;
vector<ii> assocBlock;
long long ans = 0;
void relax(int i){
if(i < n) tree[i] = max(tree[i<<1], tree[i<<1|1]);
else tree[i] = ii(0,i-n);
tree[i].first += lazy[i];
}
void create(int _n){
n = _n;
tree.assign(2*n, ii(0,0));
assocBlock.assign(n, ii(0,0));
lazy.assign(2*n,0);
for(int i = 2*n-1;i>0;i--) relax(i);
}
void update(int L, int R, long long v){
for(int l = L + n, r = R + n;l < r;l >>= 1, r >>= 1){
if(l&1){
lazy[l] += v;
relax(l);
l++;
}
if(r&1){
r--;
lazy[r] += v;
relax(r);
}
}
for(int l = L + n;l > 0;l >>= 1) relax(l);
for(int r = R + n - 1;r > 0;r >>= 1) relax(r);
}
long long query(){
ans = tree[1].first;
ii block = assocBlock[tree[1].second];
update(block.first, block.second+1, -inf);
ans += tree[1].first;
update(block.first, block.second+1, inf);
return ans;
}
};
vector<segment> trees;
segment overall;
long long n, Q, WMAX;
vector<edge> edges;
vector<ii> adj[100005];
vector<int> Cnodes;
bool cented[100005];
int sz[100005];
int dfs(int u, int p){
Cnodes.push_back(u);
sz[u] = 1;
for(ii v : adj[u]){
if(v.first == p) continue;
if(cented[v.first]) continue;
sz[u] += dfs(v.first, u);
}
return sz[u];
}
vector<ii> ranges;
int cnt = 0;
ii dfs2(int u, int p){
ii res = ii(cnt,cnt); cnt++;
for(ii v : adj[u]){
if(v.first == p) continue;
if(cented[v.first]) continue;
ii vRes = dfs2(v.first, u);
res.second = max(res.second, vRes.second);
edges[v.second].trees.push_back((int) trees.size());
edges[v.second].preorder.push_back(vRes);
if(p == -1) ranges.push_back(vRes);
}
return res;
}
void recurse(int A){
dfs(A, -1);
int R;
for(int u : Cnodes){
int maxSz = sz[A] - sz[u];
for(ii v : adj[u]){
if(cented[v.first]) continue;
if(sz[v.first] < sz[u]) maxSz = max(maxSz, sz[v.first]);
}
if(2*maxSz <= (int) sz[A]){
R = u;
break;
}
}
cnt = 0; dfs2(R, -1);
trees.push_back({});
trees.back().create(cnt);
for(ii r : ranges){
for(int i = r.first;i <= r.second;i++) trees.back().assocBlock[i] = ii(r);
}
cented[R] = true;
Cnodes.clear(); ranges.clear();
for(ii v : adj[R]){
if(!cented[v.first]) recurse(v.first);
}
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> Q >> WMAX;
for(int i = 0;i < n-1;i++){
int u, v, w; cin >> u >> v >> w; u--; v--;
edges.push_back({u,v,w,{},{}});
adj[u].push_back(ii(v,i));
adj[v].push_back(ii(u,i));
}
recurse(0);
for(edge e : edges){
for(int i = 0;i < (int) e.preorder.size();i++){
ii x = e.preorder[i];
trees[e.trees[i]].update(x.first, x.second+1, e.w);
}
}
overall.create(n);
for(int i = 0;i < n;i++) overall.update(i,i+1,trees[i].query());
long long ans = 0;
while(Q--){
long long E, w; cin >> E >> w;
E = (E + ans) % (n-1); w = (w + ans) % WMAX;
edge e = edges[E];
long long diff = w - e.w;
for(int i = 0;i < (int) e.preorder.size();i++){
ii x = e.preorder[i];
int treeNo = e.trees[i];
long long preAns = trees[treeNo].ans;
trees[treeNo].update(x.first, x.second+1, diff);
long long diff2 = trees[treeNo].query() - preAns;
overall.update(treeNo,treeNo+1,diff2);
}
edges[E].w = w;
ans = overall.tree[1].first;
cout << ans << "\n";
}
}
Compilation message
diameter.cpp: In function 'void recurse(long long int)':
diameter.cpp:103:6: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
int R;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2688 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
7 ms |
2816 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2816 KB |
Output is correct |
12 |
Correct |
6 ms |
2816 KB |
Output is correct |
13 |
Correct |
6 ms |
2816 KB |
Output is correct |
14 |
Correct |
6 ms |
2816 KB |
Output is correct |
15 |
Correct |
6 ms |
2816 KB |
Output is correct |
16 |
Correct |
6 ms |
2816 KB |
Output is correct |
17 |
Correct |
6 ms |
2816 KB |
Output is correct |
18 |
Correct |
7 ms |
2816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2688 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
7 ms |
2816 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2816 KB |
Output is correct |
12 |
Correct |
6 ms |
2816 KB |
Output is correct |
13 |
Correct |
6 ms |
2816 KB |
Output is correct |
14 |
Correct |
6 ms |
2816 KB |
Output is correct |
15 |
Correct |
6 ms |
2816 KB |
Output is correct |
16 |
Correct |
6 ms |
2816 KB |
Output is correct |
17 |
Correct |
6 ms |
2816 KB |
Output is correct |
18 |
Correct |
7 ms |
2816 KB |
Output is correct |
19 |
Correct |
29 ms |
3712 KB |
Output is correct |
20 |
Correct |
28 ms |
3712 KB |
Output is correct |
21 |
Correct |
33 ms |
3840 KB |
Output is correct |
22 |
Correct |
29 ms |
4088 KB |
Output is correct |
23 |
Correct |
49 ms |
7652 KB |
Output is correct |
24 |
Correct |
60 ms |
8796 KB |
Output is correct |
25 |
Correct |
66 ms |
9488 KB |
Output is correct |
26 |
Correct |
66 ms |
10212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
7 ms |
2688 KB |
Output is correct |
4 |
Correct |
20 ms |
3072 KB |
Output is correct |
5 |
Correct |
66 ms |
3960 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2944 KB |
Output is correct |
8 |
Correct |
8 ms |
2944 KB |
Output is correct |
9 |
Correct |
11 ms |
3072 KB |
Output is correct |
10 |
Correct |
27 ms |
3328 KB |
Output is correct |
11 |
Correct |
102 ms |
4344 KB |
Output is correct |
12 |
Correct |
13 ms |
5476 KB |
Output is correct |
13 |
Correct |
14 ms |
5476 KB |
Output is correct |
14 |
Correct |
16 ms |
5476 KB |
Output is correct |
15 |
Correct |
37 ms |
5732 KB |
Output is correct |
16 |
Correct |
130 ms |
6876 KB |
Output is correct |
17 |
Correct |
147 ms |
57296 KB |
Output is correct |
18 |
Correct |
146 ms |
57288 KB |
Output is correct |
19 |
Correct |
151 ms |
57292 KB |
Output is correct |
20 |
Correct |
185 ms |
57548 KB |
Output is correct |
21 |
Correct |
286 ms |
58956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
3712 KB |
Output is correct |
2 |
Correct |
38 ms |
3960 KB |
Output is correct |
3 |
Correct |
167 ms |
4472 KB |
Output is correct |
4 |
Correct |
316 ms |
5368 KB |
Output is correct |
5 |
Correct |
58 ms |
17208 KB |
Output is correct |
6 |
Correct |
111 ms |
17436 KB |
Output is correct |
7 |
Correct |
344 ms |
18232 KB |
Output is correct |
8 |
Correct |
622 ms |
18872 KB |
Output is correct |
9 |
Correct |
291 ms |
83832 KB |
Output is correct |
10 |
Correct |
385 ms |
83784 KB |
Output is correct |
11 |
Correct |
759 ms |
84448 KB |
Output is correct |
12 |
Correct |
1208 ms |
85340 KB |
Output is correct |
13 |
Correct |
604 ms |
170960 KB |
Output is correct |
14 |
Correct |
711 ms |
171336 KB |
Output is correct |
15 |
Correct |
1169 ms |
171976 KB |
Output is correct |
16 |
Correct |
1752 ms |
173008 KB |
Output is correct |
17 |
Correct |
2387 ms |
172524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2323 ms |
147560 KB |
Output is correct |
2 |
Correct |
2421 ms |
150408 KB |
Output is correct |
3 |
Correct |
2363 ms |
149588 KB |
Output is correct |
4 |
Correct |
2419 ms |
150356 KB |
Output is correct |
5 |
Correct |
2333 ms |
143564 KB |
Output is correct |
6 |
Correct |
1912 ms |
107592 KB |
Output is correct |
7 |
Correct |
3130 ms |
174776 KB |
Output is correct |
8 |
Correct |
3103 ms |
175184 KB |
Output is correct |
9 |
Correct |
3177 ms |
174840 KB |
Output is correct |
10 |
Correct |
3113 ms |
174236 KB |
Output is correct |
11 |
Correct |
3017 ms |
166084 KB |
Output is correct |
12 |
Correct |
2470 ms |
120768 KB |
Output is correct |
13 |
Correct |
3186 ms |
184648 KB |
Output is correct |
14 |
Correct |
3141 ms |
184656 KB |
Output is correct |
15 |
Correct |
3162 ms |
184652 KB |
Output is correct |
16 |
Correct |
3184 ms |
184020 KB |
Output is correct |
17 |
Correct |
3094 ms |
174904 KB |
Output is correct |
18 |
Correct |
2444 ms |
124436 KB |
Output is correct |
19 |
Correct |
3142 ms |
184688 KB |
Output is correct |
20 |
Correct |
3151 ms |
184572 KB |
Output is correct |
21 |
Correct |
3193 ms |
184632 KB |
Output is correct |
22 |
Correct |
3216 ms |
183920 KB |
Output is correct |
23 |
Correct |
3058 ms |
174584 KB |
Output is correct |
24 |
Correct |
2392 ms |
124712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
6 ms |
2688 KB |
Output is correct |
3 |
Correct |
6 ms |
2688 KB |
Output is correct |
4 |
Correct |
6 ms |
2688 KB |
Output is correct |
5 |
Correct |
6 ms |
2688 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
6 ms |
2688 KB |
Output is correct |
8 |
Correct |
6 ms |
2816 KB |
Output is correct |
9 |
Correct |
7 ms |
2816 KB |
Output is correct |
10 |
Correct |
6 ms |
2688 KB |
Output is correct |
11 |
Correct |
6 ms |
2816 KB |
Output is correct |
12 |
Correct |
6 ms |
2816 KB |
Output is correct |
13 |
Correct |
6 ms |
2816 KB |
Output is correct |
14 |
Correct |
6 ms |
2816 KB |
Output is correct |
15 |
Correct |
6 ms |
2816 KB |
Output is correct |
16 |
Correct |
6 ms |
2816 KB |
Output is correct |
17 |
Correct |
6 ms |
2816 KB |
Output is correct |
18 |
Correct |
7 ms |
2816 KB |
Output is correct |
19 |
Correct |
29 ms |
3712 KB |
Output is correct |
20 |
Correct |
28 ms |
3712 KB |
Output is correct |
21 |
Correct |
33 ms |
3840 KB |
Output is correct |
22 |
Correct |
29 ms |
4088 KB |
Output is correct |
23 |
Correct |
49 ms |
7652 KB |
Output is correct |
24 |
Correct |
60 ms |
8796 KB |
Output is correct |
25 |
Correct |
66 ms |
9488 KB |
Output is correct |
26 |
Correct |
66 ms |
10212 KB |
Output is correct |
27 |
Correct |
6 ms |
2688 KB |
Output is correct |
28 |
Correct |
6 ms |
2688 KB |
Output is correct |
29 |
Correct |
7 ms |
2688 KB |
Output is correct |
30 |
Correct |
20 ms |
3072 KB |
Output is correct |
31 |
Correct |
66 ms |
3960 KB |
Output is correct |
32 |
Correct |
6 ms |
2688 KB |
Output is correct |
33 |
Correct |
6 ms |
2944 KB |
Output is correct |
34 |
Correct |
8 ms |
2944 KB |
Output is correct |
35 |
Correct |
11 ms |
3072 KB |
Output is correct |
36 |
Correct |
27 ms |
3328 KB |
Output is correct |
37 |
Correct |
102 ms |
4344 KB |
Output is correct |
38 |
Correct |
13 ms |
5476 KB |
Output is correct |
39 |
Correct |
14 ms |
5476 KB |
Output is correct |
40 |
Correct |
16 ms |
5476 KB |
Output is correct |
41 |
Correct |
37 ms |
5732 KB |
Output is correct |
42 |
Correct |
130 ms |
6876 KB |
Output is correct |
43 |
Correct |
147 ms |
57296 KB |
Output is correct |
44 |
Correct |
146 ms |
57288 KB |
Output is correct |
45 |
Correct |
151 ms |
57292 KB |
Output is correct |
46 |
Correct |
185 ms |
57548 KB |
Output is correct |
47 |
Correct |
286 ms |
58956 KB |
Output is correct |
48 |
Correct |
12 ms |
3712 KB |
Output is correct |
49 |
Correct |
38 ms |
3960 KB |
Output is correct |
50 |
Correct |
167 ms |
4472 KB |
Output is correct |
51 |
Correct |
316 ms |
5368 KB |
Output is correct |
52 |
Correct |
58 ms |
17208 KB |
Output is correct |
53 |
Correct |
111 ms |
17436 KB |
Output is correct |
54 |
Correct |
344 ms |
18232 KB |
Output is correct |
55 |
Correct |
622 ms |
18872 KB |
Output is correct |
56 |
Correct |
291 ms |
83832 KB |
Output is correct |
57 |
Correct |
385 ms |
83784 KB |
Output is correct |
58 |
Correct |
759 ms |
84448 KB |
Output is correct |
59 |
Correct |
1208 ms |
85340 KB |
Output is correct |
60 |
Correct |
604 ms |
170960 KB |
Output is correct |
61 |
Correct |
711 ms |
171336 KB |
Output is correct |
62 |
Correct |
1169 ms |
171976 KB |
Output is correct |
63 |
Correct |
1752 ms |
173008 KB |
Output is correct |
64 |
Correct |
2387 ms |
172524 KB |
Output is correct |
65 |
Correct |
2323 ms |
147560 KB |
Output is correct |
66 |
Correct |
2421 ms |
150408 KB |
Output is correct |
67 |
Correct |
2363 ms |
149588 KB |
Output is correct |
68 |
Correct |
2419 ms |
150356 KB |
Output is correct |
69 |
Correct |
2333 ms |
143564 KB |
Output is correct |
70 |
Correct |
1912 ms |
107592 KB |
Output is correct |
71 |
Correct |
3130 ms |
174776 KB |
Output is correct |
72 |
Correct |
3103 ms |
175184 KB |
Output is correct |
73 |
Correct |
3177 ms |
174840 KB |
Output is correct |
74 |
Correct |
3113 ms |
174236 KB |
Output is correct |
75 |
Correct |
3017 ms |
166084 KB |
Output is correct |
76 |
Correct |
2470 ms |
120768 KB |
Output is correct |
77 |
Correct |
3186 ms |
184648 KB |
Output is correct |
78 |
Correct |
3141 ms |
184656 KB |
Output is correct |
79 |
Correct |
3162 ms |
184652 KB |
Output is correct |
80 |
Correct |
3184 ms |
184020 KB |
Output is correct |
81 |
Correct |
3094 ms |
174904 KB |
Output is correct |
82 |
Correct |
2444 ms |
124436 KB |
Output is correct |
83 |
Correct |
3142 ms |
184688 KB |
Output is correct |
84 |
Correct |
3151 ms |
184572 KB |
Output is correct |
85 |
Correct |
3193 ms |
184632 KB |
Output is correct |
86 |
Correct |
3216 ms |
183920 KB |
Output is correct |
87 |
Correct |
3058 ms |
174584 KB |
Output is correct |
88 |
Correct |
2392 ms |
124712 KB |
Output is correct |
89 |
Correct |
2343 ms |
147644 KB |
Output is correct |
90 |
Correct |
2662 ms |
158620 KB |
Output is correct |
91 |
Correct |
2997 ms |
170908 KB |
Output is correct |
92 |
Correct |
3104 ms |
173908 KB |
Output is correct |
93 |
Correct |
3248 ms |
178120 KB |
Output is correct |
94 |
Correct |
3280 ms |
180400 KB |
Output is correct |
95 |
Correct |
3220 ms |
183176 KB |
Output is correct |
96 |
Correct |
3252 ms |
182944 KB |
Output is correct |
97 |
Correct |
3203 ms |
183320 KB |
Output is correct |
98 |
Correct |
3282 ms |
183796 KB |
Output is correct |
99 |
Correct |
3187 ms |
182988 KB |
Output is correct |
100 |
Correct |
3187 ms |
183376 KB |
Output is correct |