#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces
#endif
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
for (T &x : a)
in >> x;
return in;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &a)
{
for (T x : a)
out << x << " ";
out << "\n";
return out;
}
struct SegTree
{
pair<int, int> get(int l, int r)
{
return get(0, n, 0, l, r);
}
void inc(int l, int r, int x)
{
inc(0, n, 0, l, r, x);
}
SegTree(const vector<int> &a)
{
n = a.size();
updates = vector<int>(4 * n);
b = vector<pair<int, int>>(4 * n);
build(0, n, 0, a);
}
SegTree() {}
private:
int n = 0;
vector<pair<int, int>> b = {};
vector<int> updates = {};
void push(int l, int r, int i)
{
if (l + 1 == r)
return;
updates[i * 2 + 1] += updates[i];
updates[i * 2 + 2] += updates[i];
b[i * 2 + 1].first += updates[i];
b[i * 2 + 2].first += updates[i];
updates[i] = 0;
}
pair<int, int> build(int l, int r, int i, const vector<int> &a)
{
if (l + 1 == r)
return b[i] = pair<int, int>{a[l], l};
int m = (l + r) / 2;
return b[i] = max(build(l, m, i * 2 + 1, a), build(m, r, i * 2 + 2, a));
}
pair<int, int> get(int l, int r, int i, int ql, int qr)
{
if (l >= qr || r <= ql)
return {LLONG_MIN / 2, -1};
if (l >= ql && r <= qr)
return b[i];
push(l, r, i);
int m = (l + r) / 2;
return max(get(l, m, i * 2 + 1, ql, qr), get(m, r, i * 2 + 2, ql, qr));
}
pair<int, int> inc(int l, int r, int i, int ul, int ur, int x)
{
if (l >= ur || r <= ul)
return b[i];
if (l >= ul && r <= ur)
{
updates[i] += x;
b[i].first += x;
return b[i];
}
push(l, r, i);
int m = (l + r) / 2;
return b[i] = max(inc(l, m, i * 2 + 1, ul, ur, x), inc(m, r, i * 2 + 2, ul, ur, x));
}
};
vector<vector<pair<int, int>>> adj;
vector<bool> blocked;
vector<vector<int>> pre;
struct Tree
{
int n = 0;
int level = 0;
unordered_map<int, int> pre;
vector<int> subtree;
vector<int> initial_parent;
vector<int> pre_order;
vector<int> pre_dist;
int timer = 0;
int centroid = -1;
SegTree pre_dist_seg;
void spread(int i, int p = -1)
{
n++;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
spread(c, i);
}
}
}
int find_centroid(int i, int p = -1)
{
int subtree_size = 1;
int largest_subtree = 0;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
int sub = find_centroid(c, i);
subtree_size += sub;
largest_subtree = max(largest_subtree, sub);
}
}
if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
centroid = i;
return subtree_size;
}
int dfs(int i, int d = 0, int p = -1)
{
pre[i] = timer++;
pre_order.push_back(i);
pre_dist[pre[i]] = d;
int subtree_size = 1;
if (p == -1)
initial_parent[pre[i]] = -1;
else if (initial_parent[pre[p]] == -1)
initial_parent[pre[i]] = i;
else
initial_parent[pre[i]] = initial_parent[pre[p]];
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
subtree_size += dfs(c, d + D, i);
}
}
subtree[pre[i]] = subtree_size;
return subtree_size;
}
vector<int> split()
{
blocked[centroid] = true;
vector<int> out;
for (auto [c, d] : adj[centroid])
{
if (!blocked[c])
out.push_back(c);
}
return out;
}
Tree(int start, int level) : level(level)
{
spread(start);
pre_dist = initial_parent = subtree = vector<int>(n);
find_centroid(start);
assert(centroid != -1);
dfs(centroid);
pre_dist_seg = SegTree(pre_dist);
}
int update(int a, int b, int c)
{
if (pre.count(a) != 0 && pre.count(b) != 0)
{
if (pre[a] > pre[b])
swap(a, b);
int dist_lower = pre_dist_seg.get(pre[b], pre[b] + 1).first;
int dist_upper = pre_dist_seg.get(pre[a], pre[a] + 1).first;
int old_weight = dist_lower - dist_upper;
int delta = c - old_weight;
pre_dist_seg.inc(pre[b], pre[b] + subtree[pre[b]], delta);
}
auto [dist, i] = pre_dist_seg.get(0, n);
int bad_child = initial_parent[i];
auto dist2 = pre_dist_seg.get(0, pre[bad_child]).first;
auto dist3 = pre_dist_seg.get(pre[bad_child] + subtree[pre[bad_child]], n).first;
return dist + max({dist2, dist3, 0l});
}
};
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, q, w;
cin >> n >> q >> w;
adj.resize(n);
blocked.resize(n);
pre = vector<vector<int>>(30, vector<int>(n));
vector<pair<int, int>> all_edges;
for (int i = 0; i < n - 1; i++)
{
int a, b, c;
cin >> a >> b >> c;
a--, b--;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
all_edges.push_back({a, b});
}
vector<Tree> subtrees;
subtrees.push_back(Tree(0, 0));
queue<int> todo;
todo.push(0);
vector<vector<int>> trees_using(n, {0});
while (todo.size())
{
int index = todo.front();
todo.pop();
auto out = subtrees[index].split();
for (auto x : out)
{
Tree new_tree(x, subtrees[index].level + 1);
if (new_tree.n > 1)
{
int new_index = subtrees.size();
todo.push(new_index);
for (auto i : new_tree.pre_order)
{
if (trees_using[i].back() != new_index)
trees_using[i].push_back(new_index);
}
subtrees.push_back(move(new_tree));
}
}
}
vector<int> subtree_result(subtrees.size());
set<pair<int, int>> results;
for (int i = 0; i < subtrees.size(); i++)
{
subtree_result[i] = subtrees[i].update(-1, -1, -1);
results.insert({subtree_result[i], i});
}
int last = 0;
while (q--)
{
int d, e;
cin >> d >> e;
d = (d + last) % int(n - 1);
e = (e + last) % w;
auto [a, b] = all_edges[d];
int out = 0;
for (int i : trees_using[a])
{
results.erase({subtree_result[i], i});
subtree_result[i] = subtrees[i].update(a, b, e);
results.insert({subtree_result[i], i});
}
out = prev(results.end())->first;
cout << out << "\n";
last = out;
}
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:299:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
299 | for (int i = 0; i < subtrees.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
21 ms |
1876 KB |
Output is correct |
20 |
Correct |
23 ms |
1876 KB |
Output is correct |
21 |
Correct |
26 ms |
2132 KB |
Output is correct |
22 |
Correct |
29 ms |
2516 KB |
Output is correct |
23 |
Correct |
41 ms |
8928 KB |
Output is correct |
24 |
Correct |
62 ms |
10972 KB |
Output is correct |
25 |
Correct |
58 ms |
12000 KB |
Output is correct |
26 |
Correct |
63 ms |
13804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
10 ms |
340 KB |
Output is correct |
5 |
Correct |
47 ms |
708 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
16 ms |
764 KB |
Output is correct |
11 |
Correct |
69 ms |
940 KB |
Output is correct |
12 |
Correct |
4 ms |
3152 KB |
Output is correct |
13 |
Correct |
4 ms |
3152 KB |
Output is correct |
14 |
Correct |
6 ms |
3152 KB |
Output is correct |
15 |
Correct |
22 ms |
3152 KB |
Output is correct |
16 |
Correct |
94 ms |
3576 KB |
Output is correct |
17 |
Correct |
78 ms |
56804 KB |
Output is correct |
18 |
Correct |
79 ms |
56804 KB |
Output is correct |
19 |
Correct |
100 ms |
56744 KB |
Output is correct |
20 |
Correct |
109 ms |
56756 KB |
Output is correct |
21 |
Correct |
201 ms |
56780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2132 KB |
Output is correct |
2 |
Correct |
37 ms |
2260 KB |
Output is correct |
3 |
Correct |
162 ms |
2416 KB |
Output is correct |
4 |
Correct |
333 ms |
2784 KB |
Output is correct |
5 |
Correct |
44 ms |
25640 KB |
Output is correct |
6 |
Correct |
99 ms |
25684 KB |
Output is correct |
7 |
Correct |
372 ms |
25840 KB |
Output is correct |
8 |
Correct |
675 ms |
26332 KB |
Output is correct |
9 |
Correct |
228 ms |
146836 KB |
Output is correct |
10 |
Correct |
357 ms |
146912 KB |
Output is correct |
11 |
Correct |
915 ms |
147136 KB |
Output is correct |
12 |
Correct |
1500 ms |
147464 KB |
Output is correct |
13 |
Correct |
493 ms |
309920 KB |
Output is correct |
14 |
Correct |
623 ms |
309984 KB |
Output is correct |
15 |
Correct |
1251 ms |
310340 KB |
Output is correct |
16 |
Correct |
2098 ms |
310640 KB |
Output is correct |
17 |
Correct |
3750 ms |
310552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2880 ms |
245740 KB |
Output is correct |
2 |
Correct |
3091 ms |
252528 KB |
Output is correct |
3 |
Correct |
2962 ms |
250676 KB |
Output is correct |
4 |
Correct |
3034 ms |
253172 KB |
Output is correct |
5 |
Correct |
2972 ms |
236576 KB |
Output is correct |
6 |
Correct |
2573 ms |
158100 KB |
Output is correct |
7 |
Correct |
4280 ms |
312408 KB |
Output is correct |
8 |
Correct |
4033 ms |
312364 KB |
Output is correct |
9 |
Correct |
4083 ms |
312476 KB |
Output is correct |
10 |
Correct |
4100 ms |
310856 KB |
Output is correct |
11 |
Correct |
4013 ms |
292144 KB |
Output is correct |
12 |
Correct |
3493 ms |
190204 KB |
Output is correct |
13 |
Correct |
4463 ms |
345184 KB |
Output is correct |
14 |
Correct |
4387 ms |
345196 KB |
Output is correct |
15 |
Correct |
4417 ms |
345488 KB |
Output is correct |
16 |
Correct |
4372 ms |
343372 KB |
Output is correct |
17 |
Correct |
4214 ms |
321008 KB |
Output is correct |
18 |
Correct |
3697 ms |
202432 KB |
Output is correct |
19 |
Correct |
4455 ms |
345384 KB |
Output is correct |
20 |
Correct |
4299 ms |
345280 KB |
Output is correct |
21 |
Correct |
4728 ms |
349348 KB |
Output is correct |
22 |
Correct |
4576 ms |
347492 KB |
Output is correct |
23 |
Correct |
4473 ms |
325204 KB |
Output is correct |
24 |
Correct |
3904 ms |
206584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
21 ms |
1876 KB |
Output is correct |
20 |
Correct |
23 ms |
1876 KB |
Output is correct |
21 |
Correct |
26 ms |
2132 KB |
Output is correct |
22 |
Correct |
29 ms |
2516 KB |
Output is correct |
23 |
Correct |
41 ms |
8928 KB |
Output is correct |
24 |
Correct |
62 ms |
10972 KB |
Output is correct |
25 |
Correct |
58 ms |
12000 KB |
Output is correct |
26 |
Correct |
63 ms |
13804 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
10 ms |
340 KB |
Output is correct |
31 |
Correct |
47 ms |
708 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
596 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
2 ms |
596 KB |
Output is correct |
36 |
Correct |
16 ms |
764 KB |
Output is correct |
37 |
Correct |
69 ms |
940 KB |
Output is correct |
38 |
Correct |
4 ms |
3152 KB |
Output is correct |
39 |
Correct |
4 ms |
3152 KB |
Output is correct |
40 |
Correct |
6 ms |
3152 KB |
Output is correct |
41 |
Correct |
22 ms |
3152 KB |
Output is correct |
42 |
Correct |
94 ms |
3576 KB |
Output is correct |
43 |
Correct |
78 ms |
56804 KB |
Output is correct |
44 |
Correct |
79 ms |
56804 KB |
Output is correct |
45 |
Correct |
100 ms |
56744 KB |
Output is correct |
46 |
Correct |
109 ms |
56756 KB |
Output is correct |
47 |
Correct |
201 ms |
56780 KB |
Output is correct |
48 |
Correct |
6 ms |
2132 KB |
Output is correct |
49 |
Correct |
37 ms |
2260 KB |
Output is correct |
50 |
Correct |
162 ms |
2416 KB |
Output is correct |
51 |
Correct |
333 ms |
2784 KB |
Output is correct |
52 |
Correct |
44 ms |
25640 KB |
Output is correct |
53 |
Correct |
99 ms |
25684 KB |
Output is correct |
54 |
Correct |
372 ms |
25840 KB |
Output is correct |
55 |
Correct |
675 ms |
26332 KB |
Output is correct |
56 |
Correct |
228 ms |
146836 KB |
Output is correct |
57 |
Correct |
357 ms |
146912 KB |
Output is correct |
58 |
Correct |
915 ms |
147136 KB |
Output is correct |
59 |
Correct |
1500 ms |
147464 KB |
Output is correct |
60 |
Correct |
493 ms |
309920 KB |
Output is correct |
61 |
Correct |
623 ms |
309984 KB |
Output is correct |
62 |
Correct |
1251 ms |
310340 KB |
Output is correct |
63 |
Correct |
2098 ms |
310640 KB |
Output is correct |
64 |
Correct |
3750 ms |
310552 KB |
Output is correct |
65 |
Correct |
2880 ms |
245740 KB |
Output is correct |
66 |
Correct |
3091 ms |
252528 KB |
Output is correct |
67 |
Correct |
2962 ms |
250676 KB |
Output is correct |
68 |
Correct |
3034 ms |
253172 KB |
Output is correct |
69 |
Correct |
2972 ms |
236576 KB |
Output is correct |
70 |
Correct |
2573 ms |
158100 KB |
Output is correct |
71 |
Correct |
4280 ms |
312408 KB |
Output is correct |
72 |
Correct |
4033 ms |
312364 KB |
Output is correct |
73 |
Correct |
4083 ms |
312476 KB |
Output is correct |
74 |
Correct |
4100 ms |
310856 KB |
Output is correct |
75 |
Correct |
4013 ms |
292144 KB |
Output is correct |
76 |
Correct |
3493 ms |
190204 KB |
Output is correct |
77 |
Correct |
4463 ms |
345184 KB |
Output is correct |
78 |
Correct |
4387 ms |
345196 KB |
Output is correct |
79 |
Correct |
4417 ms |
345488 KB |
Output is correct |
80 |
Correct |
4372 ms |
343372 KB |
Output is correct |
81 |
Correct |
4214 ms |
321008 KB |
Output is correct |
82 |
Correct |
3697 ms |
202432 KB |
Output is correct |
83 |
Correct |
4455 ms |
345384 KB |
Output is correct |
84 |
Correct |
4299 ms |
345280 KB |
Output is correct |
85 |
Correct |
4728 ms |
349348 KB |
Output is correct |
86 |
Correct |
4576 ms |
347492 KB |
Output is correct |
87 |
Correct |
4473 ms |
325204 KB |
Output is correct |
88 |
Correct |
3904 ms |
206584 KB |
Output is correct |
89 |
Correct |
3037 ms |
252912 KB |
Output is correct |
90 |
Correct |
3471 ms |
277760 KB |
Output is correct |
91 |
Correct |
4054 ms |
307520 KB |
Output is correct |
92 |
Correct |
4164 ms |
315728 KB |
Output is correct |
93 |
Correct |
4342 ms |
326872 KB |
Output is correct |
94 |
Correct |
4338 ms |
334708 KB |
Output is correct |
95 |
Correct |
4342 ms |
348120 KB |
Output is correct |
96 |
Correct |
4475 ms |
348064 KB |
Output is correct |
97 |
Correct |
4436 ms |
347984 KB |
Output is correct |
98 |
Correct |
4309 ms |
348524 KB |
Output is correct |
99 |
Correct |
4325 ms |
347992 KB |
Output is correct |
100 |
Correct |
4438 ms |
348104 KB |
Output is correct |