#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, 1}, {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;
for(int j = 0; j < 3; j++)
for(int k = 0; 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 = 0; k < 3; k++)
node[i].val[j][k] = max(node[lChild].val[j][k], node[rChild].val[j][k]);
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 < 9; j++)
node[i].val[j % 3][j / 3] = 0;
}
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';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
34 ms |
61904 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
34 ms |
61904 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
61816 KB |
Output is correct |
2 |
Correct |
34 ms |
61872 KB |
Output is correct |
3 |
Correct |
35 ms |
62012 KB |
Output is correct |
4 |
Correct |
54 ms |
62156 KB |
Output is correct |
5 |
Correct |
138 ms |
62976 KB |
Output is correct |
6 |
Correct |
36 ms |
61788 KB |
Output is correct |
7 |
Correct |
34 ms |
61892 KB |
Output is correct |
8 |
Correct |
34 ms |
61848 KB |
Output is correct |
9 |
Correct |
36 ms |
61904 KB |
Output is correct |
10 |
Correct |
61 ms |
62208 KB |
Output is correct |
11 |
Correct |
130 ms |
63172 KB |
Output is correct |
12 |
Correct |
39 ms |
62388 KB |
Output is correct |
13 |
Correct |
39 ms |
62412 KB |
Output is correct |
14 |
Correct |
43 ms |
62440 KB |
Output is correct |
15 |
Correct |
78 ms |
62612 KB |
Output is correct |
16 |
Correct |
145 ms |
63768 KB |
Output is correct |
17 |
Correct |
147 ms |
71648 KB |
Output is correct |
18 |
Correct |
143 ms |
71620 KB |
Output is correct |
19 |
Correct |
137 ms |
71764 KB |
Output is correct |
20 |
Correct |
168 ms |
72052 KB |
Output is correct |
21 |
Correct |
315 ms |
73380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
61932 KB |
Output is correct |
2 |
Incorrect |
57 ms |
62112 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
486 ms |
75856 KB |
Output is correct |
2 |
Correct |
519 ms |
75800 KB |
Output is correct |
3 |
Correct |
468 ms |
75812 KB |
Output is correct |
4 |
Correct |
463 ms |
75848 KB |
Output is correct |
5 |
Correct |
472 ms |
75884 KB |
Output is correct |
6 |
Correct |
428 ms |
76116 KB |
Output is correct |
7 |
Correct |
529 ms |
77484 KB |
Output is correct |
8 |
Correct |
525 ms |
77576 KB |
Output is correct |
9 |
Correct |
509 ms |
77584 KB |
Output is correct |
10 |
Correct |
546 ms |
77484 KB |
Output is correct |
11 |
Correct |
533 ms |
77464 KB |
Output is correct |
12 |
Correct |
479 ms |
77236 KB |
Output is correct |
13 |
Correct |
674 ms |
79948 KB |
Output is correct |
14 |
Correct |
636 ms |
79944 KB |
Output is correct |
15 |
Correct |
647 ms |
79948 KB |
Output is correct |
16 |
Correct |
649 ms |
79980 KB |
Output is correct |
17 |
Correct |
666 ms |
79676 KB |
Output is correct |
18 |
Correct |
521 ms |
78144 KB |
Output is correct |
19 |
Correct |
653 ms |
79936 KB |
Output is correct |
20 |
Correct |
617 ms |
79888 KB |
Output is correct |
21 |
Correct |
591 ms |
79992 KB |
Output is correct |
22 |
Correct |
658 ms |
79924 KB |
Output is correct |
23 |
Correct |
668 ms |
79792 KB |
Output is correct |
24 |
Correct |
583 ms |
78132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
34 ms |
61904 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |