#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct {
int idx;
ll val;
} pil;
int n, q;
ll w;
ll edges[101010][3];
vector<pil> adj[101010];
int ch[101010], sz[101010];
struct subtree {
int cent, tot, r, d;
vector<pil> ord;
unordered_map<int, int> in, out, depth, dir, child;
void ett(int v, ll dis, int par = -1) {
ord[++r] = {v, dis}; in[v] = r;
if (par != -1) dir[v] = d;
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i].idx;
if (u == par) continue;
if (ch[u] == 1) continue;
depth[u] = depth[v] + 1;
if (par == -1) d = u;
ett(u, dis + adj[v][i].val, v);
}
out[v] = r;
}
struct maxseg {
vector<pil> tree;
vector<ll> lazy;
pil mer(pil lt, pil rt) {
if (lt.val > rt.val) return lt;
if (lt.val < rt.val) return rt;
if (lt.val == rt.val) {
if (lt.idx > rt.idx) return lt;
else return rt;
}
}
void prop(int v, int st, int ed) {
tree[v].val += lazy[v];
if (st != ed) {
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
}
lazy[v] = 0;
}
void init(int v, int st, int ed, vector<pil>* ord) {
if (st == ed) {
tree[v] = (*ord)[st];
lazy[v] = 0;
return;
}
int mid = (st + ed) / 2;
init(2*v, st, mid, ord);
init(2*v+1, mid+1, ed, ord);
tree[v] = mer(tree[2*v], tree[2*v+1]);
}
void upd(int v, int st, int ed, int lt, int rt, ll diff) {
prop(v, st, ed);
if (lt <= st && ed <= rt) {
lazy[v] = diff;
prop(v, st, ed);
return;
}
if (st > rt || lt > ed) return;
int mid = (st + ed) / 2;
upd(2*v, st, mid, lt, rt, diff);
upd(2*v+1, mid+1, ed, lt, rt, diff);
tree[v] = mer(tree[2*v], tree[2*v+1]);
}
pil get(int v, int st, int ed, int lt, int rt) {
prop(v, st, ed);
if (lt <= st && ed <= rt) return tree[v];
if (st > rt || lt > ed) return {0, 0};
int mid = (st + ed) / 2;
return mer(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt));
}
} seg;
void init() {
r = 0;
for (int i = 0; i <= tot; i++) ord.push_back({0, 0});
seg.tree.resize(4*tot);
seg.lazy.resize(4*tot);
ett(cent, 0);
seg.init(1, 1, tot, &ord);
}
int update(int d, ll e) {
int v = (depth[edges[d][0]] > depth[edges[d][1]] ? edges[d][0] : edges[d][1]);
int u = (depth[edges[d][0]] < depth[edges[d][1]] ? edges[d][0] : edges[d][1]);
seg.upd(1, 1, tot, in[v], out[v], e - edges[d][2]);
return (u != cent ? child[dir[v]] : 0);
}
int get(ll* dst) {
pil x = seg.get(1, 1, tot, 1, tot);
int u = dir[x.idx];
pil y = seg.get(1, 1, tot, 1, in[u]-1);
pil z = seg.get(1, 1, tot, out[u]+1, tot);
*dst = max(*dst, x.val + max(y.val, z.val));
return child[u];
}
} sub[101010];
void get_sz(int v, int par = -1) {
sz[v] = 1;
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i].idx;
if (ch[u] == 1) continue;
if (u == par) continue;
get_sz(u, v);
sz[v] += sz[u];
}
}
int get_cent(int tot, int v, int par = -1) {
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i].idx;
if (ch[u] == 1) continue;
if (u == par) continue;
if (sz[u] * 2 > tot) return get_cent(tot, u, v);
}
return v;
}
int cent(int v, int tot) {
get_sz(v);
v = get_cent(tot, v);
get_sz(v);
sub[v].tot = tot;
sub[v].cent = v;
sub[v].init();
ch[v] = 1;
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i].idx;
if (ch[u] == 1) continue;
sub[v].child[u] = cent(u, sz[u]);
}
return v;
}
void update(int cent, int d, ll e) {
while (sub[cent].tot > 1) {
cent = sub[cent].update(d, e);
}
}
void get(int cent, ll* dst) {
while (sub[cent].tot > 1) {
cent = sub[cent].get(dst);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q >> w;
for (int i = 1; i < n; i++) {
int a, b; ll c;
cin >> a >> b >> c;
edges[i][0] = a;
edges[i][1] = b;
edges[i][2] = c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
int CENT = cent(1, n);
ll last = 0;
while (q--) {
int d; ll e;
cin >> d >> e;
d = (d + last) % (n - 1) + 1;
e = (e + last) % w;
update(CENT, d, e);
edges[d][2] = e;
last = -1;
get(CENT, &last);
cout << last << "\n";
}
return 0;
}
Compilation message
diameter.cpp: In member function 'void subtree::ett(int, ll, int)':
diameter.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 0; i < adj[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'void get_sz(int, int)':
diameter.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < adj[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int get_cent(int, int, int)':
diameter.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int i = 0; i < adj[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int cent(int, int)':
diameter.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pil>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int i = 0; i < adj[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~
diameter.cpp: In member function 'pil subtree::maxseg::mer(pil, pil)':
diameter.cpp:45:9: warning: control reaches end of non-void function [-Wreturn-type]
45 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
41816 KB |
Output is correct |
2 |
Correct |
10 ms |
41564 KB |
Output is correct |
3 |
Correct |
9 ms |
41560 KB |
Output is correct |
4 |
Correct |
9 ms |
41564 KB |
Output is correct |
5 |
Correct |
9 ms |
41564 KB |
Output is correct |
6 |
Correct |
9 ms |
41564 KB |
Output is correct |
7 |
Correct |
9 ms |
41564 KB |
Output is correct |
8 |
Correct |
11 ms |
41564 KB |
Output is correct |
9 |
Correct |
9 ms |
41564 KB |
Output is correct |
10 |
Correct |
9 ms |
41564 KB |
Output is correct |
11 |
Correct |
9 ms |
41564 KB |
Output is correct |
12 |
Correct |
9 ms |
41744 KB |
Output is correct |
13 |
Correct |
9 ms |
41804 KB |
Output is correct |
14 |
Correct |
10 ms |
41564 KB |
Output is correct |
15 |
Correct |
9 ms |
41564 KB |
Output is correct |
16 |
Correct |
10 ms |
41604 KB |
Output is correct |
17 |
Correct |
9 ms |
42072 KB |
Output is correct |
18 |
Correct |
9 ms |
41820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
41816 KB |
Output is correct |
2 |
Correct |
10 ms |
41564 KB |
Output is correct |
3 |
Correct |
9 ms |
41560 KB |
Output is correct |
4 |
Correct |
9 ms |
41564 KB |
Output is correct |
5 |
Correct |
9 ms |
41564 KB |
Output is correct |
6 |
Correct |
9 ms |
41564 KB |
Output is correct |
7 |
Correct |
9 ms |
41564 KB |
Output is correct |
8 |
Correct |
11 ms |
41564 KB |
Output is correct |
9 |
Correct |
9 ms |
41564 KB |
Output is correct |
10 |
Correct |
9 ms |
41564 KB |
Output is correct |
11 |
Correct |
9 ms |
41564 KB |
Output is correct |
12 |
Correct |
9 ms |
41744 KB |
Output is correct |
13 |
Correct |
9 ms |
41804 KB |
Output is correct |
14 |
Correct |
10 ms |
41564 KB |
Output is correct |
15 |
Correct |
9 ms |
41564 KB |
Output is correct |
16 |
Correct |
10 ms |
41604 KB |
Output is correct |
17 |
Correct |
9 ms |
42072 KB |
Output is correct |
18 |
Correct |
9 ms |
41820 KB |
Output is correct |
19 |
Correct |
29 ms |
43660 KB |
Output is correct |
20 |
Correct |
33 ms |
43860 KB |
Output is correct |
21 |
Correct |
31 ms |
44128 KB |
Output is correct |
22 |
Correct |
31 ms |
44576 KB |
Output is correct |
23 |
Correct |
52 ms |
52856 KB |
Output is correct |
24 |
Correct |
64 ms |
55888 KB |
Output is correct |
25 |
Correct |
96 ms |
58004 KB |
Output is correct |
26 |
Correct |
75 ms |
60456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
41564 KB |
Output is correct |
2 |
Correct |
9 ms |
41616 KB |
Output is correct |
3 |
Correct |
10 ms |
41696 KB |
Output is correct |
4 |
Correct |
17 ms |
41564 KB |
Output is correct |
5 |
Correct |
50 ms |
42068 KB |
Output is correct |
6 |
Correct |
9 ms |
41820 KB |
Output is correct |
7 |
Correct |
10 ms |
42076 KB |
Output is correct |
8 |
Correct |
10 ms |
42072 KB |
Output is correct |
9 |
Correct |
11 ms |
42076 KB |
Output is correct |
10 |
Correct |
22 ms |
42076 KB |
Output is correct |
11 |
Correct |
70 ms |
42324 KB |
Output is correct |
12 |
Correct |
16 ms |
45660 KB |
Output is correct |
13 |
Correct |
15 ms |
45656 KB |
Output is correct |
14 |
Correct |
16 ms |
45660 KB |
Output is correct |
15 |
Correct |
31 ms |
45660 KB |
Output is correct |
16 |
Correct |
119 ms |
46368 KB |
Output is correct |
17 |
Correct |
154 ms |
125760 KB |
Output is correct |
18 |
Correct |
161 ms |
125596 KB |
Output is correct |
19 |
Correct |
154 ms |
125756 KB |
Output is correct |
20 |
Correct |
191 ms |
126180 KB |
Output is correct |
21 |
Correct |
271 ms |
126256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
44124 KB |
Output is correct |
2 |
Correct |
38 ms |
44280 KB |
Output is correct |
3 |
Correct |
138 ms |
44304 KB |
Output is correct |
4 |
Correct |
258 ms |
44792 KB |
Output is correct |
5 |
Correct |
73 ms |
76756 KB |
Output is correct |
6 |
Correct |
129 ms |
76780 KB |
Output is correct |
7 |
Correct |
407 ms |
77044 KB |
Output is correct |
8 |
Correct |
688 ms |
77664 KB |
Output is correct |
9 |
Correct |
402 ms |
250168 KB |
Output is correct |
10 |
Correct |
508 ms |
250344 KB |
Output is correct |
11 |
Correct |
940 ms |
250472 KB |
Output is correct |
12 |
Correct |
1512 ms |
251084 KB |
Output is correct |
13 |
Correct |
843 ms |
487100 KB |
Output is correct |
14 |
Correct |
989 ms |
487156 KB |
Output is correct |
15 |
Correct |
1561 ms |
487220 KB |
Output is correct |
16 |
Correct |
2291 ms |
487900 KB |
Output is correct |
17 |
Correct |
3242 ms |
487732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2731 ms |
387776 KB |
Output is correct |
2 |
Correct |
2808 ms |
398128 KB |
Output is correct |
3 |
Correct |
2737 ms |
395100 KB |
Output is correct |
4 |
Correct |
2821 ms |
401380 KB |
Output is correct |
5 |
Correct |
2699 ms |
376744 KB |
Output is correct |
6 |
Correct |
2418 ms |
269592 KB |
Output is correct |
7 |
Correct |
3877 ms |
495936 KB |
Output is correct |
8 |
Correct |
3825 ms |
495528 KB |
Output is correct |
9 |
Correct |
3725 ms |
500072 KB |
Output is correct |
10 |
Correct |
3714 ms |
497820 KB |
Output is correct |
11 |
Correct |
3575 ms |
472376 KB |
Output is correct |
12 |
Correct |
3244 ms |
322876 KB |
Output is correct |
13 |
Correct |
3850 ms |
539856 KB |
Output is correct |
14 |
Correct |
3796 ms |
539848 KB |
Output is correct |
15 |
Correct |
3822 ms |
540072 KB |
Output is correct |
16 |
Correct |
3863 ms |
537684 KB |
Output is correct |
17 |
Correct |
3722 ms |
507188 KB |
Output is correct |
18 |
Correct |
3159 ms |
335716 KB |
Output is correct |
19 |
Correct |
3802 ms |
539796 KB |
Output is correct |
20 |
Correct |
3754 ms |
539860 KB |
Output is correct |
21 |
Correct |
3985 ms |
540036 KB |
Output is correct |
22 |
Correct |
3729 ms |
537800 KB |
Output is correct |
23 |
Correct |
3630 ms |
506988 KB |
Output is correct |
24 |
Correct |
3080 ms |
335716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
41816 KB |
Output is correct |
2 |
Correct |
10 ms |
41564 KB |
Output is correct |
3 |
Correct |
9 ms |
41560 KB |
Output is correct |
4 |
Correct |
9 ms |
41564 KB |
Output is correct |
5 |
Correct |
9 ms |
41564 KB |
Output is correct |
6 |
Correct |
9 ms |
41564 KB |
Output is correct |
7 |
Correct |
9 ms |
41564 KB |
Output is correct |
8 |
Correct |
11 ms |
41564 KB |
Output is correct |
9 |
Correct |
9 ms |
41564 KB |
Output is correct |
10 |
Correct |
9 ms |
41564 KB |
Output is correct |
11 |
Correct |
9 ms |
41564 KB |
Output is correct |
12 |
Correct |
9 ms |
41744 KB |
Output is correct |
13 |
Correct |
9 ms |
41804 KB |
Output is correct |
14 |
Correct |
10 ms |
41564 KB |
Output is correct |
15 |
Correct |
9 ms |
41564 KB |
Output is correct |
16 |
Correct |
10 ms |
41604 KB |
Output is correct |
17 |
Correct |
9 ms |
42072 KB |
Output is correct |
18 |
Correct |
9 ms |
41820 KB |
Output is correct |
19 |
Correct |
29 ms |
43660 KB |
Output is correct |
20 |
Correct |
33 ms |
43860 KB |
Output is correct |
21 |
Correct |
31 ms |
44128 KB |
Output is correct |
22 |
Correct |
31 ms |
44576 KB |
Output is correct |
23 |
Correct |
52 ms |
52856 KB |
Output is correct |
24 |
Correct |
64 ms |
55888 KB |
Output is correct |
25 |
Correct |
96 ms |
58004 KB |
Output is correct |
26 |
Correct |
75 ms |
60456 KB |
Output is correct |
27 |
Correct |
9 ms |
41564 KB |
Output is correct |
28 |
Correct |
9 ms |
41616 KB |
Output is correct |
29 |
Correct |
10 ms |
41696 KB |
Output is correct |
30 |
Correct |
17 ms |
41564 KB |
Output is correct |
31 |
Correct |
50 ms |
42068 KB |
Output is correct |
32 |
Correct |
9 ms |
41820 KB |
Output is correct |
33 |
Correct |
10 ms |
42076 KB |
Output is correct |
34 |
Correct |
10 ms |
42072 KB |
Output is correct |
35 |
Correct |
11 ms |
42076 KB |
Output is correct |
36 |
Correct |
22 ms |
42076 KB |
Output is correct |
37 |
Correct |
70 ms |
42324 KB |
Output is correct |
38 |
Correct |
16 ms |
45660 KB |
Output is correct |
39 |
Correct |
15 ms |
45656 KB |
Output is correct |
40 |
Correct |
16 ms |
45660 KB |
Output is correct |
41 |
Correct |
31 ms |
45660 KB |
Output is correct |
42 |
Correct |
119 ms |
46368 KB |
Output is correct |
43 |
Correct |
154 ms |
125760 KB |
Output is correct |
44 |
Correct |
161 ms |
125596 KB |
Output is correct |
45 |
Correct |
154 ms |
125756 KB |
Output is correct |
46 |
Correct |
191 ms |
126180 KB |
Output is correct |
47 |
Correct |
271 ms |
126256 KB |
Output is correct |
48 |
Correct |
18 ms |
44124 KB |
Output is correct |
49 |
Correct |
38 ms |
44280 KB |
Output is correct |
50 |
Correct |
138 ms |
44304 KB |
Output is correct |
51 |
Correct |
258 ms |
44792 KB |
Output is correct |
52 |
Correct |
73 ms |
76756 KB |
Output is correct |
53 |
Correct |
129 ms |
76780 KB |
Output is correct |
54 |
Correct |
407 ms |
77044 KB |
Output is correct |
55 |
Correct |
688 ms |
77664 KB |
Output is correct |
56 |
Correct |
402 ms |
250168 KB |
Output is correct |
57 |
Correct |
508 ms |
250344 KB |
Output is correct |
58 |
Correct |
940 ms |
250472 KB |
Output is correct |
59 |
Correct |
1512 ms |
251084 KB |
Output is correct |
60 |
Correct |
843 ms |
487100 KB |
Output is correct |
61 |
Correct |
989 ms |
487156 KB |
Output is correct |
62 |
Correct |
1561 ms |
487220 KB |
Output is correct |
63 |
Correct |
2291 ms |
487900 KB |
Output is correct |
64 |
Correct |
3242 ms |
487732 KB |
Output is correct |
65 |
Correct |
2731 ms |
387776 KB |
Output is correct |
66 |
Correct |
2808 ms |
398128 KB |
Output is correct |
67 |
Correct |
2737 ms |
395100 KB |
Output is correct |
68 |
Correct |
2821 ms |
401380 KB |
Output is correct |
69 |
Correct |
2699 ms |
376744 KB |
Output is correct |
70 |
Correct |
2418 ms |
269592 KB |
Output is correct |
71 |
Correct |
3877 ms |
495936 KB |
Output is correct |
72 |
Correct |
3825 ms |
495528 KB |
Output is correct |
73 |
Correct |
3725 ms |
500072 KB |
Output is correct |
74 |
Correct |
3714 ms |
497820 KB |
Output is correct |
75 |
Correct |
3575 ms |
472376 KB |
Output is correct |
76 |
Correct |
3244 ms |
322876 KB |
Output is correct |
77 |
Correct |
3850 ms |
539856 KB |
Output is correct |
78 |
Correct |
3796 ms |
539848 KB |
Output is correct |
79 |
Correct |
3822 ms |
540072 KB |
Output is correct |
80 |
Correct |
3863 ms |
537684 KB |
Output is correct |
81 |
Correct |
3722 ms |
507188 KB |
Output is correct |
82 |
Correct |
3159 ms |
335716 KB |
Output is correct |
83 |
Correct |
3802 ms |
539796 KB |
Output is correct |
84 |
Correct |
3754 ms |
539860 KB |
Output is correct |
85 |
Correct |
3985 ms |
540036 KB |
Output is correct |
86 |
Correct |
3729 ms |
537800 KB |
Output is correct |
87 |
Correct |
3630 ms |
506988 KB |
Output is correct |
88 |
Correct |
3080 ms |
335716 KB |
Output is correct |
89 |
Correct |
2770 ms |
397296 KB |
Output is correct |
90 |
Correct |
3099 ms |
439264 KB |
Output is correct |
91 |
Correct |
3651 ms |
486984 KB |
Output is correct |
92 |
Correct |
3684 ms |
498260 KB |
Output is correct |
93 |
Correct |
3983 ms |
514516 KB |
Output is correct |
94 |
Correct |
3834 ms |
521132 KB |
Output is correct |
95 |
Correct |
3706 ms |
537128 KB |
Output is correct |
96 |
Correct |
3831 ms |
536028 KB |
Output is correct |
97 |
Correct |
3843 ms |
536820 KB |
Output is correct |
98 |
Correct |
3779 ms |
539152 KB |
Output is correct |
99 |
Correct |
3873 ms |
536548 KB |
Output is correct |
100 |
Correct |
3763 ms |
536424 KB |
Output is correct |