#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
int deb, fin, tag, val[3][3];
};
const int M = 1 << 18, N = 2*M, INF = 1e18 + 42;
Node node[N];
vector<int> adj[N];
int n, q, w, id = 0, h[M], l[M], r[M], a[M], b[M], c[M];
int coeff[3][3] = {{1, -1, 0}, {0, -2, -1}, {0, 0, 1}};
void eulertour(int i = 0, int pre = 0, int depth = 0) {
l[i] = id;
h[i] = depth;
depth++, id++;
for(int j : adj[i])
if(j != pre) {
eulertour(j, i, depth);
id++;
}
r[i] = id;
}
inline void applyOp(int i, int add) {
node[i].tag += add;
if(node[i].fin - node[i].deb == 1) {
for(int j = 0; j < 3; j++)
node[i].val[j][j] += coeff[j][j] * add;
} else if(node[i].fin - node[i].deb == 2) {
for(int j = 0; j < 3; j++)
for(int k = j; k < 3; k++)
node[i].val[j][k] += coeff[j][k] * add;
node[i].val[0][2] = -INF;
} else {
for(int j = 0; j < 3; j++)
for(int k = j; k < 3; k++)
node[i].val[j][k] += coeff[j][k] * add;
}
}
void update(int i, int d, int f, int add) {
if(node[i].fin <= d || f <= node[i].deb)
return;
if(d <= node[i].deb && node[i].fin <= f) {
applyOp(i, add);
return;
}
int lChild = i*2, rChild = i*2+1;
applyOp(lChild, node[i].tag);
applyOp(rChild, node[i].tag);
node[i].tag = 0;
update(lChild, d, f, add);
update(rChild, d, f, add);
for(int j = 0; j < 3; j++)
for(int k = j; k < 3; k++)
node[i].val[j][k] = max(max(node[lChild].val[j][k], node[rChild].val[j][k]), -INF);
for(int j = 0; j < 3; j++)
for(int k = j; k < 3; k++)
for(int l = k+1; l < 3; l++)
node[i].val[j][l] = max(node[i].val[j][l], node[lChild].val[j][k] + node[rChild].val[k+1][l]);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i = 0; i < N; i++) {
node[i].tag = 0;
for(int j = 0; j < 3; j++)
for(int k = j; k < 3; k++)
node[i].val[j][k] = 0;
if(i >= M/2)
node[i].val[0][2] = -INF;
if(i >= M) {
node[i].val[0][1] = -INF;
node[i].val[1][2] = -INF;
}
}
for(int i = M; i < N; i++)
node[i].fin = 1 + (node[i].deb = i - M);
for(int i = M-1; i > 0; i--)
node[i].deb = node[i*2].deb,
node[i].fin = node[i*2+1].fin;
cin >> n >> q >> w;
for(int i = 0; i < n-1; i++) {
cin >> a[i] >> b[i] >> c[i];
a[i]--, b[i]--;
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
eulertour();
for(int i = 0; i < n-1; i++) {
if(h[a[i]] > h[b[i]])
swap(a[i], b[i]);
update(1, l[b[i]], r[b[i]], c[i]);
}
int last = 0;
for(int i = 0; i < q; i++) {
int d, e; cin >> d >> e;
d = (d + last) % (n-1);
e = (e + last) % w;
update(1, l[b[d]], r[b[d]], e - c[d]);
c[d] = e;
last = node[1].val[0][2];
cout << last << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
61868 KB |
Output is correct |
2 |
Correct |
38 ms |
61872 KB |
Output is correct |
3 |
Correct |
39 ms |
61924 KB |
Output is correct |
4 |
Correct |
35 ms |
61844 KB |
Output is correct |
5 |
Correct |
34 ms |
61868 KB |
Output is correct |
6 |
Correct |
34 ms |
61872 KB |
Output is correct |
7 |
Correct |
35 ms |
61872 KB |
Output is correct |
8 |
Correct |
45 ms |
61864 KB |
Output is correct |
9 |
Correct |
46 ms |
61908 KB |
Output is correct |
10 |
Correct |
41 ms |
61932 KB |
Output is correct |
11 |
Correct |
34 ms |
61896 KB |
Output is correct |
12 |
Correct |
37 ms |
61876 KB |
Output is correct |
13 |
Correct |
43 ms |
61828 KB |
Output is correct |
14 |
Correct |
38 ms |
61912 KB |
Output is correct |
15 |
Correct |
40 ms |
61872 KB |
Output is correct |
16 |
Correct |
40 ms |
61864 KB |
Output is correct |
17 |
Correct |
37 ms |
61868 KB |
Output is correct |
18 |
Correct |
47 ms |
61868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
61868 KB |
Output is correct |
2 |
Correct |
38 ms |
61872 KB |
Output is correct |
3 |
Correct |
39 ms |
61924 KB |
Output is correct |
4 |
Correct |
35 ms |
61844 KB |
Output is correct |
5 |
Correct |
34 ms |
61868 KB |
Output is correct |
6 |
Correct |
34 ms |
61872 KB |
Output is correct |
7 |
Correct |
35 ms |
61872 KB |
Output is correct |
8 |
Correct |
45 ms |
61864 KB |
Output is correct |
9 |
Correct |
46 ms |
61908 KB |
Output is correct |
10 |
Correct |
41 ms |
61932 KB |
Output is correct |
11 |
Correct |
34 ms |
61896 KB |
Output is correct |
12 |
Correct |
37 ms |
61876 KB |
Output is correct |
13 |
Correct |
43 ms |
61828 KB |
Output is correct |
14 |
Correct |
38 ms |
61912 KB |
Output is correct |
15 |
Correct |
40 ms |
61872 KB |
Output is correct |
16 |
Correct |
40 ms |
61864 KB |
Output is correct |
17 |
Correct |
37 ms |
61868 KB |
Output is correct |
18 |
Correct |
47 ms |
61868 KB |
Output is correct |
19 |
Correct |
56 ms |
62064 KB |
Output is correct |
20 |
Correct |
47 ms |
61996 KB |
Output is correct |
21 |
Correct |
44 ms |
62000 KB |
Output is correct |
22 |
Correct |
43 ms |
62084 KB |
Output is correct |
23 |
Correct |
54 ms |
62472 KB |
Output is correct |
24 |
Correct |
56 ms |
62412 KB |
Output is correct |
25 |
Correct |
49 ms |
62484 KB |
Output is correct |
26 |
Correct |
53 ms |
62704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
61896 KB |
Output is correct |
2 |
Correct |
33 ms |
61808 KB |
Output is correct |
3 |
Correct |
41 ms |
61832 KB |
Output is correct |
4 |
Correct |
61 ms |
62088 KB |
Output is correct |
5 |
Correct |
131 ms |
63116 KB |
Output is correct |
6 |
Correct |
35 ms |
61900 KB |
Output is correct |
7 |
Correct |
35 ms |
61952 KB |
Output is correct |
8 |
Correct |
35 ms |
61900 KB |
Output is correct |
9 |
Correct |
38 ms |
61884 KB |
Output is correct |
10 |
Correct |
65 ms |
62156 KB |
Output is correct |
11 |
Correct |
140 ms |
63204 KB |
Output is correct |
12 |
Correct |
40 ms |
62308 KB |
Output is correct |
13 |
Correct |
38 ms |
62376 KB |
Output is correct |
14 |
Correct |
41 ms |
62412 KB |
Output is correct |
15 |
Correct |
67 ms |
62628 KB |
Output is correct |
16 |
Correct |
147 ms |
63872 KB |
Output is correct |
17 |
Correct |
128 ms |
71664 KB |
Output is correct |
18 |
Correct |
146 ms |
71712 KB |
Output is correct |
19 |
Correct |
138 ms |
71724 KB |
Output is correct |
20 |
Correct |
172 ms |
72048 KB |
Output is correct |
21 |
Correct |
288 ms |
73272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
62028 KB |
Output is correct |
2 |
Correct |
55 ms |
62156 KB |
Output is correct |
3 |
Correct |
105 ms |
62692 KB |
Output is correct |
4 |
Correct |
161 ms |
63332 KB |
Output is correct |
5 |
Correct |
46 ms |
62900 KB |
Output is correct |
6 |
Correct |
59 ms |
63028 KB |
Output is correct |
7 |
Correct |
117 ms |
63680 KB |
Output is correct |
8 |
Correct |
166 ms |
64452 KB |
Output is correct |
9 |
Correct |
94 ms |
67000 KB |
Output is correct |
10 |
Correct |
107 ms |
67088 KB |
Output is correct |
11 |
Correct |
178 ms |
67792 KB |
Output is correct |
12 |
Correct |
252 ms |
68632 KB |
Output is correct |
13 |
Correct |
160 ms |
72028 KB |
Output is correct |
14 |
Correct |
162 ms |
72244 KB |
Output is correct |
15 |
Correct |
247 ms |
72924 KB |
Output is correct |
16 |
Correct |
316 ms |
73700 KB |
Output is correct |
17 |
Correct |
354 ms |
73500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
437 ms |
75900 KB |
Output is correct |
2 |
Correct |
475 ms |
75912 KB |
Output is correct |
3 |
Correct |
455 ms |
75960 KB |
Output is correct |
4 |
Correct |
404 ms |
75880 KB |
Output is correct |
5 |
Correct |
401 ms |
75860 KB |
Output is correct |
6 |
Correct |
412 ms |
76104 KB |
Output is correct |
7 |
Correct |
506 ms |
77484 KB |
Output is correct |
8 |
Correct |
462 ms |
77512 KB |
Output is correct |
9 |
Correct |
481 ms |
77576 KB |
Output is correct |
10 |
Correct |
468 ms |
77496 KB |
Output is correct |
11 |
Correct |
442 ms |
77440 KB |
Output is correct |
12 |
Correct |
420 ms |
77264 KB |
Output is correct |
13 |
Correct |
605 ms |
79924 KB |
Output is correct |
14 |
Correct |
549 ms |
79964 KB |
Output is correct |
15 |
Correct |
560 ms |
80052 KB |
Output is correct |
16 |
Correct |
637 ms |
80088 KB |
Output is correct |
17 |
Correct |
551 ms |
79572 KB |
Output is correct |
18 |
Correct |
464 ms |
78112 KB |
Output is correct |
19 |
Correct |
612 ms |
79948 KB |
Output is correct |
20 |
Correct |
550 ms |
79896 KB |
Output is correct |
21 |
Correct |
599 ms |
79948 KB |
Output is correct |
22 |
Correct |
544 ms |
79948 KB |
Output is correct |
23 |
Correct |
568 ms |
79648 KB |
Output is correct |
24 |
Correct |
472 ms |
78104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
61868 KB |
Output is correct |
2 |
Correct |
38 ms |
61872 KB |
Output is correct |
3 |
Correct |
39 ms |
61924 KB |
Output is correct |
4 |
Correct |
35 ms |
61844 KB |
Output is correct |
5 |
Correct |
34 ms |
61868 KB |
Output is correct |
6 |
Correct |
34 ms |
61872 KB |
Output is correct |
7 |
Correct |
35 ms |
61872 KB |
Output is correct |
8 |
Correct |
45 ms |
61864 KB |
Output is correct |
9 |
Correct |
46 ms |
61908 KB |
Output is correct |
10 |
Correct |
41 ms |
61932 KB |
Output is correct |
11 |
Correct |
34 ms |
61896 KB |
Output is correct |
12 |
Correct |
37 ms |
61876 KB |
Output is correct |
13 |
Correct |
43 ms |
61828 KB |
Output is correct |
14 |
Correct |
38 ms |
61912 KB |
Output is correct |
15 |
Correct |
40 ms |
61872 KB |
Output is correct |
16 |
Correct |
40 ms |
61864 KB |
Output is correct |
17 |
Correct |
37 ms |
61868 KB |
Output is correct |
18 |
Correct |
47 ms |
61868 KB |
Output is correct |
19 |
Correct |
56 ms |
62064 KB |
Output is correct |
20 |
Correct |
47 ms |
61996 KB |
Output is correct |
21 |
Correct |
44 ms |
62000 KB |
Output is correct |
22 |
Correct |
43 ms |
62084 KB |
Output is correct |
23 |
Correct |
54 ms |
62472 KB |
Output is correct |
24 |
Correct |
56 ms |
62412 KB |
Output is correct |
25 |
Correct |
49 ms |
62484 KB |
Output is correct |
26 |
Correct |
53 ms |
62704 KB |
Output is correct |
27 |
Correct |
34 ms |
61896 KB |
Output is correct |
28 |
Correct |
33 ms |
61808 KB |
Output is correct |
29 |
Correct |
41 ms |
61832 KB |
Output is correct |
30 |
Correct |
61 ms |
62088 KB |
Output is correct |
31 |
Correct |
131 ms |
63116 KB |
Output is correct |
32 |
Correct |
35 ms |
61900 KB |
Output is correct |
33 |
Correct |
35 ms |
61952 KB |
Output is correct |
34 |
Correct |
35 ms |
61900 KB |
Output is correct |
35 |
Correct |
38 ms |
61884 KB |
Output is correct |
36 |
Correct |
65 ms |
62156 KB |
Output is correct |
37 |
Correct |
140 ms |
63204 KB |
Output is correct |
38 |
Correct |
40 ms |
62308 KB |
Output is correct |
39 |
Correct |
38 ms |
62376 KB |
Output is correct |
40 |
Correct |
41 ms |
62412 KB |
Output is correct |
41 |
Correct |
67 ms |
62628 KB |
Output is correct |
42 |
Correct |
147 ms |
63872 KB |
Output is correct |
43 |
Correct |
128 ms |
71664 KB |
Output is correct |
44 |
Correct |
146 ms |
71712 KB |
Output is correct |
45 |
Correct |
138 ms |
71724 KB |
Output is correct |
46 |
Correct |
172 ms |
72048 KB |
Output is correct |
47 |
Correct |
288 ms |
73272 KB |
Output is correct |
48 |
Correct |
49 ms |
62028 KB |
Output is correct |
49 |
Correct |
55 ms |
62156 KB |
Output is correct |
50 |
Correct |
105 ms |
62692 KB |
Output is correct |
51 |
Correct |
161 ms |
63332 KB |
Output is correct |
52 |
Correct |
46 ms |
62900 KB |
Output is correct |
53 |
Correct |
59 ms |
63028 KB |
Output is correct |
54 |
Correct |
117 ms |
63680 KB |
Output is correct |
55 |
Correct |
166 ms |
64452 KB |
Output is correct |
56 |
Correct |
94 ms |
67000 KB |
Output is correct |
57 |
Correct |
107 ms |
67088 KB |
Output is correct |
58 |
Correct |
178 ms |
67792 KB |
Output is correct |
59 |
Correct |
252 ms |
68632 KB |
Output is correct |
60 |
Correct |
160 ms |
72028 KB |
Output is correct |
61 |
Correct |
162 ms |
72244 KB |
Output is correct |
62 |
Correct |
247 ms |
72924 KB |
Output is correct |
63 |
Correct |
316 ms |
73700 KB |
Output is correct |
64 |
Correct |
354 ms |
73500 KB |
Output is correct |
65 |
Correct |
437 ms |
75900 KB |
Output is correct |
66 |
Correct |
475 ms |
75912 KB |
Output is correct |
67 |
Correct |
455 ms |
75960 KB |
Output is correct |
68 |
Correct |
404 ms |
75880 KB |
Output is correct |
69 |
Correct |
401 ms |
75860 KB |
Output is correct |
70 |
Correct |
412 ms |
76104 KB |
Output is correct |
71 |
Correct |
506 ms |
77484 KB |
Output is correct |
72 |
Correct |
462 ms |
77512 KB |
Output is correct |
73 |
Correct |
481 ms |
77576 KB |
Output is correct |
74 |
Correct |
468 ms |
77496 KB |
Output is correct |
75 |
Correct |
442 ms |
77440 KB |
Output is correct |
76 |
Correct |
420 ms |
77264 KB |
Output is correct |
77 |
Correct |
605 ms |
79924 KB |
Output is correct |
78 |
Correct |
549 ms |
79964 KB |
Output is correct |
79 |
Correct |
560 ms |
80052 KB |
Output is correct |
80 |
Correct |
637 ms |
80088 KB |
Output is correct |
81 |
Correct |
551 ms |
79572 KB |
Output is correct |
82 |
Correct |
464 ms |
78112 KB |
Output is correct |
83 |
Correct |
612 ms |
79948 KB |
Output is correct |
84 |
Correct |
550 ms |
79896 KB |
Output is correct |
85 |
Correct |
599 ms |
79948 KB |
Output is correct |
86 |
Correct |
544 ms |
79948 KB |
Output is correct |
87 |
Correct |
568 ms |
79648 KB |
Output is correct |
88 |
Correct |
472 ms |
78104 KB |
Output is correct |
89 |
Correct |
411 ms |
74860 KB |
Output is correct |
90 |
Correct |
388 ms |
75212 KB |
Output is correct |
91 |
Correct |
467 ms |
76116 KB |
Output is correct |
92 |
Correct |
459 ms |
76132 KB |
Output is correct |
93 |
Correct |
486 ms |
77628 KB |
Output is correct |
94 |
Correct |
522 ms |
76856 KB |
Output is correct |
95 |
Correct |
587 ms |
77840 KB |
Output is correct |
96 |
Correct |
569 ms |
77120 KB |
Output is correct |
97 |
Correct |
565 ms |
77828 KB |
Output is correct |
98 |
Correct |
555 ms |
79180 KB |
Output is correct |
99 |
Correct |
610 ms |
77672 KB |
Output is correct |
100 |
Correct |
575 ms |
77528 KB |
Output is correct |