#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 4e5+10;
vector<pair<int,int>> g[maxn];
pair<int,int> back[maxn];
int n, q;
int dist[maxn], cost[maxn], w;
void dfs(int u, int p) {
for(auto [v, id] : g[u]) {
if(v != p) {
dist[v] = dist[u] + cost[id];
dfs(v, u);
}
}
}
void brute() {
int last = 0;
while(q--) {
int d, e; scanf("%d %d", &d, &e);
d = (d + last) % (n - 1);
e = (e + last) % w;
cost[d] = e;
dist[1] = 0;
dfs(1, 0);
int x = (int)(max_element(dist+1, dist+n+1) - dist);
dist[x] = 0;
dfs(x, 0);
printf("%d\n", *max_element(dist+1, dist+n+1));
last = *max_element(dist+1, dist+n+1);
}
exit(0);
}
void bst() {
multiset<int, greater<int>> st;
for(int i = 0; i < n-1; i++)
st.insert(cost[i]);
int last = 0;
while(q--) {
int d, e; scanf("%d %d", &d, &e);
d = (int)((d + last) % (n - 1));
e = (int)((e + last) % w);
st.erase(st.find(cost[d]));
cost[d] = e;
st.insert(e);
last = (int)(*st.begin() + (n>2?*next(st.begin()):0));
printf("%d\n", last);
}
exit(0);
}
struct SegmentTree
{
pair<int,int> tree[maxn], G[maxn];
void build(int node) {
sort(g[node].begin(), g[node].end());
reverse(g[node].begin(), g[node].end());
if(g[node].size() == 3 || (g[node].size() == 2 && node>1) || g[node].size() == 1)
g[node].pop_back();
reverse(g[node].begin(), g[node].end());
// printf("%d == ", node);
// for(auto x : g[node])
// printf("%d ", x.first);
// printf("\n");
if(g[node].size()) {
G[node].first = g[node][0].second;
assert(g[node][0].first == 2*node);
build(node<<1);
}
else G[node].first = maxn-10;
if(g[node].size() > 1) {
G[node].second = g[node][1].second;
assert(g[node][1].first == 2*node+1);
build(node<<1|1);
}
else G[node].second = maxn-10;
int vl = tree[2*node].first + cost[G[node].first],
vr = tree[2*node+1].first + cost[G[node].second];
tree[node] = {max(vl, vr),
max({vl+vr, tree[2*node].second, tree[2*node+1].second})};
// printf("%d %d %d\n", node, tree[node].first, tree[node].second);
}
void upd(int node) {
int vl = tree[2*node].first + cost[G[node].first],
vr = tree[2*node+1].first + cost[G[node].second];
tree[node] = {max(vl, vr),
max({vl+vr, tree[2*node].second, tree[2*node+1].second})};
if(node != 1) upd(node>>1);
}
int query() { return tree[1].second; }
} seg;
void solve_seg() {
seg.build(1);
// printf("%d\n", seg.query());
int last = 0;
while(q--) {
int d, e; scanf("%d %d", &d, &e);
d = (int)((d + last) % (n - 1));
e = (int)((e + last) % w);
cost[d] = e;
auto [a, b] = back[d];
if(a > b) swap(a, b);
seg.upd(a);
last = seg.query();
printf("%d\n", last);
}
}
int main() {
scanf("%d %d %d", &n, &q, &w);
// printf("%d %d %d\n", n, q, w);
if(w > 10000) assert(0);
for(int i = 0; i < n-1; i++) {
int a, b; int c; scanf("%d %d %d", &a, &b, &c);
// printf("%d %d %d\n", a, b, c);
g[a].push_back({b, i});
g[b].push_back({a, i});
cost[i] = c;
back[i] = {a, b};
}
if((int)g[1].size() == n-1) bst();
if(n <= 5000) brute();
solve_seg();
}
Compilation message
diameter.cpp: In function 'void brute()':
diameter.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
25 | int d, e; scanf("%d %d", &d, &e);
| ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void bst()':
diameter.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
46 | int d, e; scanf("%d %d", &d, &e);
| ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void solve_seg()':
diameter.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
109 | int d, e; scanf("%d %d", &d, &e);
| ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
122 | scanf("%d %d %d", &n, &q, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:126:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
126 | int a, b; int c; scanf("%d %d %d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
7 ms |
9708 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
7 ms |
9708 KB |
Output is correct |
7 |
Correct |
7 ms |
9708 KB |
Output is correct |
8 |
Correct |
7 ms |
9708 KB |
Output is correct |
9 |
Correct |
7 ms |
9708 KB |
Output is correct |
10 |
Correct |
8 ms |
9708 KB |
Output is correct |
11 |
Correct |
7 ms |
9708 KB |
Output is correct |
12 |
Correct |
7 ms |
9708 KB |
Output is correct |
13 |
Correct |
7 ms |
9708 KB |
Output is correct |
14 |
Correct |
7 ms |
9708 KB |
Output is correct |
15 |
Correct |
7 ms |
9708 KB |
Output is correct |
16 |
Correct |
7 ms |
9708 KB |
Output is correct |
17 |
Correct |
9 ms |
9708 KB |
Output is correct |
18 |
Correct |
7 ms |
9708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
7 ms |
9708 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
7 ms |
9708 KB |
Output is correct |
7 |
Correct |
7 ms |
9708 KB |
Output is correct |
8 |
Correct |
7 ms |
9708 KB |
Output is correct |
9 |
Correct |
7 ms |
9708 KB |
Output is correct |
10 |
Correct |
8 ms |
9708 KB |
Output is correct |
11 |
Correct |
7 ms |
9708 KB |
Output is correct |
12 |
Correct |
7 ms |
9708 KB |
Output is correct |
13 |
Correct |
7 ms |
9708 KB |
Output is correct |
14 |
Correct |
7 ms |
9708 KB |
Output is correct |
15 |
Correct |
7 ms |
9708 KB |
Output is correct |
16 |
Correct |
7 ms |
9708 KB |
Output is correct |
17 |
Correct |
9 ms |
9708 KB |
Output is correct |
18 |
Correct |
7 ms |
9708 KB |
Output is correct |
19 |
Correct |
159 ms |
9836 KB |
Output is correct |
20 |
Correct |
162 ms |
9836 KB |
Output is correct |
21 |
Correct |
194 ms |
9836 KB |
Output is correct |
22 |
Correct |
213 ms |
9992 KB |
Output is correct |
23 |
Correct |
1125 ms |
10484 KB |
Output is correct |
24 |
Correct |
1211 ms |
10496 KB |
Output is correct |
25 |
Correct |
1306 ms |
10604 KB |
Output is correct |
26 |
Correct |
1532 ms |
10604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
8 ms |
9708 KB |
Output is correct |
4 |
Correct |
16 ms |
9964 KB |
Output is correct |
5 |
Correct |
52 ms |
10988 KB |
Output is correct |
6 |
Correct |
7 ms |
9708 KB |
Output is correct |
7 |
Correct |
7 ms |
9836 KB |
Output is correct |
8 |
Correct |
7 ms |
9836 KB |
Output is correct |
9 |
Correct |
8 ms |
9836 KB |
Output is correct |
10 |
Correct |
17 ms |
10092 KB |
Output is correct |
11 |
Correct |
61 ms |
11244 KB |
Output is correct |
12 |
Correct |
10 ms |
10220 KB |
Output is correct |
13 |
Correct |
10 ms |
10220 KB |
Output is correct |
14 |
Correct |
11 ms |
10348 KB |
Output is correct |
15 |
Correct |
23 ms |
10604 KB |
Output is correct |
16 |
Correct |
69 ms |
11756 KB |
Output is correct |
17 |
Correct |
78 ms |
20704 KB |
Output is correct |
18 |
Correct |
74 ms |
20704 KB |
Output is correct |
19 |
Correct |
76 ms |
20704 KB |
Output is correct |
20 |
Correct |
93 ms |
21088 KB |
Output is correct |
21 |
Correct |
246 ms |
22496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
9836 KB |
Output is correct |
2 |
Correct |
215 ms |
9964 KB |
Output is correct |
3 |
Correct |
1057 ms |
10732 KB |
Output is correct |
4 |
Correct |
2177 ms |
11552 KB |
Output is correct |
5 |
Correct |
12 ms |
10604 KB |
Output is correct |
6 |
Correct |
16 ms |
10732 KB |
Output is correct |
7 |
Correct |
33 ms |
11360 KB |
Output is correct |
8 |
Correct |
50 ms |
12140 KB |
Output is correct |
9 |
Correct |
30 ms |
13932 KB |
Output is correct |
10 |
Correct |
34 ms |
14060 KB |
Output is correct |
11 |
Correct |
50 ms |
14700 KB |
Output is correct |
12 |
Correct |
71 ms |
15468 KB |
Output is correct |
13 |
Correct |
55 ms |
18028 KB |
Output is correct |
14 |
Correct |
57 ms |
18156 KB |
Output is correct |
15 |
Correct |
79 ms |
18796 KB |
Output is correct |
16 |
Correct |
95 ms |
19692 KB |
Output is correct |
17 |
Correct |
101 ms |
19436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
148 ms |
20688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
7 ms |
9708 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
7 ms |
9708 KB |
Output is correct |
7 |
Correct |
7 ms |
9708 KB |
Output is correct |
8 |
Correct |
7 ms |
9708 KB |
Output is correct |
9 |
Correct |
7 ms |
9708 KB |
Output is correct |
10 |
Correct |
8 ms |
9708 KB |
Output is correct |
11 |
Correct |
7 ms |
9708 KB |
Output is correct |
12 |
Correct |
7 ms |
9708 KB |
Output is correct |
13 |
Correct |
7 ms |
9708 KB |
Output is correct |
14 |
Correct |
7 ms |
9708 KB |
Output is correct |
15 |
Correct |
7 ms |
9708 KB |
Output is correct |
16 |
Correct |
7 ms |
9708 KB |
Output is correct |
17 |
Correct |
9 ms |
9708 KB |
Output is correct |
18 |
Correct |
7 ms |
9708 KB |
Output is correct |
19 |
Correct |
159 ms |
9836 KB |
Output is correct |
20 |
Correct |
162 ms |
9836 KB |
Output is correct |
21 |
Correct |
194 ms |
9836 KB |
Output is correct |
22 |
Correct |
213 ms |
9992 KB |
Output is correct |
23 |
Correct |
1125 ms |
10484 KB |
Output is correct |
24 |
Correct |
1211 ms |
10496 KB |
Output is correct |
25 |
Correct |
1306 ms |
10604 KB |
Output is correct |
26 |
Correct |
1532 ms |
10604 KB |
Output is correct |
27 |
Correct |
7 ms |
9708 KB |
Output is correct |
28 |
Correct |
7 ms |
9708 KB |
Output is correct |
29 |
Correct |
8 ms |
9708 KB |
Output is correct |
30 |
Correct |
16 ms |
9964 KB |
Output is correct |
31 |
Correct |
52 ms |
10988 KB |
Output is correct |
32 |
Correct |
7 ms |
9708 KB |
Output is correct |
33 |
Correct |
7 ms |
9836 KB |
Output is correct |
34 |
Correct |
7 ms |
9836 KB |
Output is correct |
35 |
Correct |
8 ms |
9836 KB |
Output is correct |
36 |
Correct |
17 ms |
10092 KB |
Output is correct |
37 |
Correct |
61 ms |
11244 KB |
Output is correct |
38 |
Correct |
10 ms |
10220 KB |
Output is correct |
39 |
Correct |
10 ms |
10220 KB |
Output is correct |
40 |
Correct |
11 ms |
10348 KB |
Output is correct |
41 |
Correct |
23 ms |
10604 KB |
Output is correct |
42 |
Correct |
69 ms |
11756 KB |
Output is correct |
43 |
Correct |
78 ms |
20704 KB |
Output is correct |
44 |
Correct |
74 ms |
20704 KB |
Output is correct |
45 |
Correct |
76 ms |
20704 KB |
Output is correct |
46 |
Correct |
93 ms |
21088 KB |
Output is correct |
47 |
Correct |
246 ms |
22496 KB |
Output is correct |
48 |
Correct |
29 ms |
9836 KB |
Output is correct |
49 |
Correct |
215 ms |
9964 KB |
Output is correct |
50 |
Correct |
1057 ms |
10732 KB |
Output is correct |
51 |
Correct |
2177 ms |
11552 KB |
Output is correct |
52 |
Correct |
12 ms |
10604 KB |
Output is correct |
53 |
Correct |
16 ms |
10732 KB |
Output is correct |
54 |
Correct |
33 ms |
11360 KB |
Output is correct |
55 |
Correct |
50 ms |
12140 KB |
Output is correct |
56 |
Correct |
30 ms |
13932 KB |
Output is correct |
57 |
Correct |
34 ms |
14060 KB |
Output is correct |
58 |
Correct |
50 ms |
14700 KB |
Output is correct |
59 |
Correct |
71 ms |
15468 KB |
Output is correct |
60 |
Correct |
55 ms |
18028 KB |
Output is correct |
61 |
Correct |
57 ms |
18156 KB |
Output is correct |
62 |
Correct |
79 ms |
18796 KB |
Output is correct |
63 |
Correct |
95 ms |
19692 KB |
Output is correct |
64 |
Correct |
101 ms |
19436 KB |
Output is correct |
65 |
Incorrect |
148 ms |
20688 KB |
Output isn't correct |
66 |
Halted |
0 ms |
0 KB |
- |