#include<bits/stdc++.h>
using namespace std;
#define pb push_back
constexpr int maxn = 2e5+10;
int filho[maxn], in[maxn], out[maxn], t;
long long cost[maxn];
vector<pair<int,int>> g[maxn];
void dfs(int u, int p) {
in[u] = out[u] = ++t;
for(auto [v, id] : g[u]) {
if(v != p) {
filho[id] = v;
dfs(v, u);
out[u] = ++t; // eu me readiciono para os meus filhos me verem
}
}
}
template<int N>
struct SegmentTree
{
struct Node
{
long long a, b, ab, ba, aba, lazy;
Node() {
a = b = ab = ba = aba = lazy = 0;
}
Node operator+(Node other) {
Node ret;
ret.a = max(a, other.a);
ret.b = max(b, other.b);
ret.ab = max({ab, other.ab, a + other.b});
ret.ba = max({ba, other.ba, b + other.a});
ret.aba = max({aba, other.aba, ab + other.a, a + other.ba});
// lazy should always be 0
return ret;
}
} tree[4*N];
void flush(int node, int i, int j) {
if(!tree[node].lazy) return;
long long& lz = tree[node].lazy;
tree[node].a += lz;
tree[node].b -= 2*lz;
tree[node].ab -= lz;
tree[node].ba -= lz;
if(i != j) {
tree[node<<1].lazy += lz;
tree[node<<1|1].lazy += lz;
}
lz = 0;
}
void upd(int l, int r, long long v, int node = 1, int i = 1, int j = N) {
flush(node, i, j);
if(i > r || j < l) return;
if(i >= l && j <= r) {
tree[node].lazy = v;
flush(node, i, j);
return;
}
int m = (i+j) >> 1;
upd(l, r, v, node<<1, i, m);
upd(l, r, v, node<<1|1, m+1, j);
tree[node] = tree[node<<1] + tree[node<<1|1];
}
long long query() { flush(1, 1, N); return tree[1].aba; }
};
SegmentTree<maxn> seg;
int main() {
int n, q; long long w; scanf("%d %d %lld", &n, &q, &w);
for(int i = 0; i < n-1; i++) {
int a, b; long long c; scanf("%d %d %lld", &a, &b, &c);
g[a].pb({b, i});
g[b].pb({a, i});
cost[i] = c;
}
dfs(1, 0);
for(int i = 0; i < n-1; i++) {
int u = filho[i];
seg.upd(in[u], out[u], cost[i]);
}
long long last = 0;
while(q--) {
int d; long long e; scanf("%d %lld", &d, &e);
d = (int)((d + last) % (n - 1));
e = (e + last) % w;
seg.upd(in[filho[d]], out[filho[d]], e - cost[d]);
cost[d] = e;
last = seg.query();
printf("%lld\n", last);
}
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:82:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
82 | int n, q; long long w; scanf("%d %d %lld", &n, &q, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:84:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | int a, b; long long c; scanf("%d %d %lld", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:96:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
96 | int d; long long e; scanf("%d %lld", &d, &e);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
25 ms |
42604 KB |
Output is correct |
6 |
Correct |
30 ms |
42604 KB |
Output is correct |
7 |
Correct |
27 ms |
42604 KB |
Output is correct |
8 |
Correct |
26 ms |
42732 KB |
Output is correct |
9 |
Correct |
26 ms |
42604 KB |
Output is correct |
10 |
Correct |
26 ms |
42624 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
26 ms |
42604 KB |
Output is correct |
13 |
Correct |
30 ms |
42604 KB |
Output is correct |
14 |
Correct |
26 ms |
42604 KB |
Output is correct |
15 |
Correct |
25 ms |
42604 KB |
Output is correct |
16 |
Correct |
27 ms |
42624 KB |
Output is correct |
17 |
Correct |
26 ms |
42604 KB |
Output is correct |
18 |
Correct |
26 ms |
42732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
25 ms |
42604 KB |
Output is correct |
6 |
Correct |
30 ms |
42604 KB |
Output is correct |
7 |
Correct |
27 ms |
42604 KB |
Output is correct |
8 |
Correct |
26 ms |
42732 KB |
Output is correct |
9 |
Correct |
26 ms |
42604 KB |
Output is correct |
10 |
Correct |
26 ms |
42624 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
26 ms |
42604 KB |
Output is correct |
13 |
Correct |
30 ms |
42604 KB |
Output is correct |
14 |
Correct |
26 ms |
42604 KB |
Output is correct |
15 |
Correct |
25 ms |
42604 KB |
Output is correct |
16 |
Correct |
27 ms |
42624 KB |
Output is correct |
17 |
Correct |
26 ms |
42604 KB |
Output is correct |
18 |
Correct |
26 ms |
42732 KB |
Output is correct |
19 |
Correct |
33 ms |
42732 KB |
Output is correct |
20 |
Correct |
32 ms |
42732 KB |
Output is correct |
21 |
Correct |
34 ms |
42956 KB |
Output is correct |
22 |
Correct |
35 ms |
42860 KB |
Output is correct |
23 |
Correct |
41 ms |
43116 KB |
Output is correct |
24 |
Correct |
39 ms |
43116 KB |
Output is correct |
25 |
Correct |
39 ms |
43116 KB |
Output is correct |
26 |
Correct |
42 ms |
43372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
42624 KB |
Output is correct |
2 |
Correct |
27 ms |
42604 KB |
Output is correct |
3 |
Correct |
28 ms |
42604 KB |
Output is correct |
4 |
Correct |
49 ms |
42860 KB |
Output is correct |
5 |
Correct |
105 ms |
43756 KB |
Output is correct |
6 |
Correct |
27 ms |
42604 KB |
Output is correct |
7 |
Correct |
27 ms |
42604 KB |
Output is correct |
8 |
Correct |
26 ms |
42604 KB |
Output is correct |
9 |
Correct |
28 ms |
42860 KB |
Output is correct |
10 |
Correct |
42 ms |
42860 KB |
Output is correct |
11 |
Correct |
107 ms |
44012 KB |
Output is correct |
12 |
Correct |
30 ms |
42988 KB |
Output is correct |
13 |
Correct |
30 ms |
42988 KB |
Output is correct |
14 |
Correct |
36 ms |
43048 KB |
Output is correct |
15 |
Correct |
49 ms |
43244 KB |
Output is correct |
16 |
Correct |
127 ms |
44524 KB |
Output is correct |
17 |
Correct |
106 ms |
49632 KB |
Output is correct |
18 |
Correct |
113 ms |
49760 KB |
Output is correct |
19 |
Correct |
131 ms |
49760 KB |
Output is correct |
20 |
Correct |
138 ms |
50272 KB |
Output is correct |
21 |
Correct |
251 ms |
51296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
42700 KB |
Output is correct |
2 |
Correct |
38 ms |
42792 KB |
Output is correct |
3 |
Correct |
87 ms |
43500 KB |
Output is correct |
4 |
Correct |
144 ms |
44140 KB |
Output is correct |
5 |
Correct |
40 ms |
43372 KB |
Output is correct |
6 |
Correct |
50 ms |
43500 KB |
Output is correct |
7 |
Correct |
105 ms |
44140 KB |
Output is correct |
8 |
Correct |
184 ms |
44908 KB |
Output is correct |
9 |
Correct |
80 ms |
46316 KB |
Output is correct |
10 |
Correct |
97 ms |
46700 KB |
Output is correct |
11 |
Correct |
163 ms |
47212 KB |
Output is correct |
12 |
Correct |
254 ms |
48108 KB |
Output is correct |
13 |
Correct |
144 ms |
50156 KB |
Output is correct |
14 |
Correct |
171 ms |
50212 KB |
Output is correct |
15 |
Correct |
230 ms |
51052 KB |
Output is correct |
16 |
Correct |
354 ms |
51692 KB |
Output is correct |
17 |
Correct |
273 ms |
51564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
463 ms |
53996 KB |
Output is correct |
2 |
Correct |
468 ms |
53920 KB |
Output is correct |
3 |
Correct |
451 ms |
53868 KB |
Output is correct |
4 |
Correct |
458 ms |
53996 KB |
Output is correct |
5 |
Correct |
467 ms |
53996 KB |
Output is correct |
6 |
Correct |
372 ms |
54120 KB |
Output is correct |
7 |
Correct |
584 ms |
56172 KB |
Output is correct |
8 |
Correct |
524 ms |
56300 KB |
Output is correct |
9 |
Correct |
505 ms |
56172 KB |
Output is correct |
10 |
Correct |
502 ms |
56428 KB |
Output is correct |
11 |
Correct |
480 ms |
56172 KB |
Output is correct |
12 |
Correct |
483 ms |
55780 KB |
Output is correct |
13 |
Correct |
671 ms |
59492 KB |
Output is correct |
14 |
Correct |
603 ms |
59500 KB |
Output is correct |
15 |
Correct |
608 ms |
59628 KB |
Output is correct |
16 |
Correct |
619 ms |
59852 KB |
Output is correct |
17 |
Correct |
562 ms |
59116 KB |
Output is correct |
18 |
Correct |
501 ms |
57060 KB |
Output is correct |
19 |
Correct |
604 ms |
59500 KB |
Output is correct |
20 |
Correct |
602 ms |
59500 KB |
Output is correct |
21 |
Correct |
595 ms |
59652 KB |
Output is correct |
22 |
Correct |
635 ms |
59628 KB |
Output is correct |
23 |
Correct |
591 ms |
59064 KB |
Output is correct |
24 |
Correct |
465 ms |
56932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
42604 KB |
Output is correct |
2 |
Correct |
25 ms |
42604 KB |
Output is correct |
3 |
Correct |
25 ms |
42604 KB |
Output is correct |
4 |
Correct |
25 ms |
42604 KB |
Output is correct |
5 |
Correct |
25 ms |
42604 KB |
Output is correct |
6 |
Correct |
30 ms |
42604 KB |
Output is correct |
7 |
Correct |
27 ms |
42604 KB |
Output is correct |
8 |
Correct |
26 ms |
42732 KB |
Output is correct |
9 |
Correct |
26 ms |
42604 KB |
Output is correct |
10 |
Correct |
26 ms |
42624 KB |
Output is correct |
11 |
Correct |
25 ms |
42604 KB |
Output is correct |
12 |
Correct |
26 ms |
42604 KB |
Output is correct |
13 |
Correct |
30 ms |
42604 KB |
Output is correct |
14 |
Correct |
26 ms |
42604 KB |
Output is correct |
15 |
Correct |
25 ms |
42604 KB |
Output is correct |
16 |
Correct |
27 ms |
42624 KB |
Output is correct |
17 |
Correct |
26 ms |
42604 KB |
Output is correct |
18 |
Correct |
26 ms |
42732 KB |
Output is correct |
19 |
Correct |
33 ms |
42732 KB |
Output is correct |
20 |
Correct |
32 ms |
42732 KB |
Output is correct |
21 |
Correct |
34 ms |
42956 KB |
Output is correct |
22 |
Correct |
35 ms |
42860 KB |
Output is correct |
23 |
Correct |
41 ms |
43116 KB |
Output is correct |
24 |
Correct |
39 ms |
43116 KB |
Output is correct |
25 |
Correct |
39 ms |
43116 KB |
Output is correct |
26 |
Correct |
42 ms |
43372 KB |
Output is correct |
27 |
Correct |
26 ms |
42624 KB |
Output is correct |
28 |
Correct |
27 ms |
42604 KB |
Output is correct |
29 |
Correct |
28 ms |
42604 KB |
Output is correct |
30 |
Correct |
49 ms |
42860 KB |
Output is correct |
31 |
Correct |
105 ms |
43756 KB |
Output is correct |
32 |
Correct |
27 ms |
42604 KB |
Output is correct |
33 |
Correct |
27 ms |
42604 KB |
Output is correct |
34 |
Correct |
26 ms |
42604 KB |
Output is correct |
35 |
Correct |
28 ms |
42860 KB |
Output is correct |
36 |
Correct |
42 ms |
42860 KB |
Output is correct |
37 |
Correct |
107 ms |
44012 KB |
Output is correct |
38 |
Correct |
30 ms |
42988 KB |
Output is correct |
39 |
Correct |
30 ms |
42988 KB |
Output is correct |
40 |
Correct |
36 ms |
43048 KB |
Output is correct |
41 |
Correct |
49 ms |
43244 KB |
Output is correct |
42 |
Correct |
127 ms |
44524 KB |
Output is correct |
43 |
Correct |
106 ms |
49632 KB |
Output is correct |
44 |
Correct |
113 ms |
49760 KB |
Output is correct |
45 |
Correct |
131 ms |
49760 KB |
Output is correct |
46 |
Correct |
138 ms |
50272 KB |
Output is correct |
47 |
Correct |
251 ms |
51296 KB |
Output is correct |
48 |
Correct |
28 ms |
42700 KB |
Output is correct |
49 |
Correct |
38 ms |
42792 KB |
Output is correct |
50 |
Correct |
87 ms |
43500 KB |
Output is correct |
51 |
Correct |
144 ms |
44140 KB |
Output is correct |
52 |
Correct |
40 ms |
43372 KB |
Output is correct |
53 |
Correct |
50 ms |
43500 KB |
Output is correct |
54 |
Correct |
105 ms |
44140 KB |
Output is correct |
55 |
Correct |
184 ms |
44908 KB |
Output is correct |
56 |
Correct |
80 ms |
46316 KB |
Output is correct |
57 |
Correct |
97 ms |
46700 KB |
Output is correct |
58 |
Correct |
163 ms |
47212 KB |
Output is correct |
59 |
Correct |
254 ms |
48108 KB |
Output is correct |
60 |
Correct |
144 ms |
50156 KB |
Output is correct |
61 |
Correct |
171 ms |
50212 KB |
Output is correct |
62 |
Correct |
230 ms |
51052 KB |
Output is correct |
63 |
Correct |
354 ms |
51692 KB |
Output is correct |
64 |
Correct |
273 ms |
51564 KB |
Output is correct |
65 |
Correct |
463 ms |
53996 KB |
Output is correct |
66 |
Correct |
468 ms |
53920 KB |
Output is correct |
67 |
Correct |
451 ms |
53868 KB |
Output is correct |
68 |
Correct |
458 ms |
53996 KB |
Output is correct |
69 |
Correct |
467 ms |
53996 KB |
Output is correct |
70 |
Correct |
372 ms |
54120 KB |
Output is correct |
71 |
Correct |
584 ms |
56172 KB |
Output is correct |
72 |
Correct |
524 ms |
56300 KB |
Output is correct |
73 |
Correct |
505 ms |
56172 KB |
Output is correct |
74 |
Correct |
502 ms |
56428 KB |
Output is correct |
75 |
Correct |
480 ms |
56172 KB |
Output is correct |
76 |
Correct |
483 ms |
55780 KB |
Output is correct |
77 |
Correct |
671 ms |
59492 KB |
Output is correct |
78 |
Correct |
603 ms |
59500 KB |
Output is correct |
79 |
Correct |
608 ms |
59628 KB |
Output is correct |
80 |
Correct |
619 ms |
59852 KB |
Output is correct |
81 |
Correct |
562 ms |
59116 KB |
Output is correct |
82 |
Correct |
501 ms |
57060 KB |
Output is correct |
83 |
Correct |
604 ms |
59500 KB |
Output is correct |
84 |
Correct |
602 ms |
59500 KB |
Output is correct |
85 |
Correct |
595 ms |
59652 KB |
Output is correct |
86 |
Correct |
635 ms |
59628 KB |
Output is correct |
87 |
Correct |
591 ms |
59064 KB |
Output is correct |
88 |
Correct |
465 ms |
56932 KB |
Output is correct |
89 |
Correct |
463 ms |
52948 KB |
Output is correct |
90 |
Correct |
422 ms |
53356 KB |
Output is correct |
91 |
Correct |
467 ms |
54508 KB |
Output is correct |
92 |
Correct |
474 ms |
54380 KB |
Output is correct |
93 |
Correct |
506 ms |
56684 KB |
Output is correct |
94 |
Correct |
558 ms |
55692 KB |
Output is correct |
95 |
Correct |
579 ms |
56920 KB |
Output is correct |
96 |
Correct |
589 ms |
56044 KB |
Output is correct |
97 |
Correct |
662 ms |
56892 KB |
Output is correct |
98 |
Correct |
629 ms |
58728 KB |
Output is correct |
99 |
Correct |
624 ms |
56604 KB |
Output is correct |
100 |
Correct |
627 ms |
56684 KB |
Output is correct |