#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Node {
long long maxim;
long long lazy;
Node() {
maxim = lazy = 0;
}
};
class SegTree {
public:
int n;
Node* aint;
void init(int _n, vector<long long>v) {
n = _n;
aint = new Node[4 * n + 5];
for (int i = 0; i < v.size(); ++i)
update(1, 1, n, i + 1, v[i]);
}
void update(int node, int l, int r, int pos, long long val) {
if (l == r) {
aint[node].maxim = val;
aint[node].lazy = 0;
return ;
}
int m = (l + r) / 2;
if (pos <= m)
update(2 * node, l, m, pos, val);
else
update(2 * node + 1, m + 1, r, pos, val);
aint[node] = join(aint[2 * node], aint[2 * node + 1]);
}
void updateL(int node, int l, int r, int x, int y, long long val) {
if (x <= l && r <= y) {
aint[node].lazy += val;
propag(node, r - l + 1);
return ;
}
propag(node, r - l + 1);
if (r < x)
return ;
if (l > y)
return ;
int m = (r + l) / 2;
updateL(2 * node, l, m, x, y, val);
updateL(2 * node + 1, m + 1, r, x, y, val);
aint[node] = join(aint[2 * node], aint[2 * node + 1]);
}
long long query() {
propag(1, n);
return aint[1].maxim;
}
Node join(Node a, Node b) {
Node aux;
aux.maxim = max(a.maxim, b.maxim);
aux.lazy = 0;
return aux;
}
void propag(int node, int len) {
aint[node].maxim += aint[node].lazy;
if (len > 1) {
aint[2 * node].lazy += aint[node].lazy;
aint[2 * node + 1].lazy += aint[node].lazy;
}
aint[node].lazy = 0;
}
void updL(pair<int, int>aux, long long val) {
updateL(1, 1, n, aux.first, aux.second, val);
}
};
class Comp {
public:
vector<SegTree>v1;
vector<vector< pair<int, int> > >v2;
multiset<long long>s1;
} cp[MAXN];
multiset<long long>ans1;
map<pair<int, int>, int>mp;
map<pair<int, int>, pair<int, int> >posComp;
vector<int>wComp[MAXN];
set<pair<int, long long> >G[MAXN];
long long cost[MAXN];
int tsz;
int sz[MAXN];
void getSize(int v, int f) {
sz[v] = 1;
for (auto it:G[v])
if (it.first != f) {
getSize(it.first, v);
sz[v] += sz[it.first];
}
}
int getc(int node, int f) {
for (auto it:G[node])
if (it.first != f && tsz / 2 < sz[it.first])
return getc(it.first, node);
return node;
}
int k, ind, ind1 = 0;
long long dist[MAXN];
int lin[MAXN], first[MAXN], last[MAXN];
pair<int, pair<int, int> >mc[MAXN];
void dfs1(int node, int f) {
lin[++ind] = node;
first[node] = ind;
for (auto it:G[node])
if (it.first != f) {
ind1++;
int auxind = ind1;
mc[ind1].first = mp[{it.first, node}];
mc[ind1].second.first = ind + 1;
dist[it.first] = dist[node] + it.second;
dfs1(it.first, node);
mc[auxind].second.second = ind;
}
last[node] = ind;
}
void dfs(int node) {
getSize(node, 0);
tsz = sz[node];
int c = getc(node, 0);
++k;
int j = 0;
for (auto it:G[c]) {
j++;
ind = 0;
ind1 = 1;
dist[it.first] = it.second;
dfs1(it.first, c);
vector<long long>aux;
for (int i = 1; i <= ind; ++i)
aux.push_back(dist[lin[i]]);
SegTree aux1;
aux1.init(ind, aux);
cp[k].v1.push_back(aux1);
cp[k].s1.insert(aux1.query());
vector<pair<int, int> >aux2;
int cmm = mp[{it.first, c}];
posComp[{k, cmm}] = {j, 1};
aux2.push_back({1, ind});
wComp[cmm].push_back(k);
for (int i = 2; i <= ind1; ++i) {
posComp[{k, mc[i].first}] = {j, i};
aux2.push_back(mc[i].second);
wComp[mc[i].first].push_back(k);
}
cp[k].v2.push_back(aux2);
G[it.first].erase({c, it.second});
}
if (!cp[k].s1.empty()) {
long long ans = 0;
multiset<long long>::iterator it1 = cp[k].s1.end();
it1--;
ans += (*it1);
if (it1 != cp[k].s1.begin()) {
it1--;
ans += (*it1);
}
ans1.insert(ans);
}
for (auto it:G[c])
dfs(it.first);
}
void upd(int ed, long long nc) {
for (auto it:wComp[ed]) {
pair<int, int>aux = posComp[{it, ed}];
long long ans = 0;
multiset<long long>::iterator it1 = cp[it].s1.end();
it1--;
ans += (*it1);
if (it1 != cp[it].s1.begin()) {
it1--;
ans += (*it1);
}
ans1.erase(ans1.find(ans));
cp[it].s1.erase(cp[it].s1.find(cp[it].v1[aux.first - 1].query()));
cp[it].v1[aux.first - 1].updL(cp[it].v2[aux.first - 1][aux.second - 1], nc - cost[ed]);
cp[it].s1.insert(cp[it].v1[aux.first - 1].query());
ans = 0;
it1 = cp[it].s1.end();
it1--;
ans += (*it1);
if (it1 != cp[it].s1.begin()) {
it1--;
ans += (*it1);
}
ans1.insert(ans);
}
cost[ed] = nc;
}
long long qry() {
multiset<long long>::iterator it = ans1.end();
it--;
return (*it);
}
int main() {
ios::sync_with_stdio(0);
cin.tie();
//freopen("date.in", "r", stdin);
//freopen("date.out", "w", stdout);
int n, q;
long long w;
cin >> n >> q >> w;
for (int i = 1; i < n; ++i) {
int x, y;
long long z;
cin >> x >> y >> z;
mp[{x, y}] = mp[{y, x}] = i;
G[x].insert({y, z});
G[y].insert({x, z});
cost[i] = z;
}
dfs(1);
long long last = 0;
for (int i = 1; i <= q; ++i) {
int d;
long long e;
cin >> d >> e;
d = (d + last) % (n - 1) + 1;
e = (e + last) % w;
upd(d, e);
last = qry();
cout << last << '\n';
}
return 0;
}
Compilation message
diameter.cpp: In member function 'void SegTree::init(int, std::vector<long long int>)':
diameter.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); ++i)
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16760 KB |
Output is correct |
2 |
Correct |
16 ms |
16760 KB |
Output is correct |
3 |
Correct |
16 ms |
16760 KB |
Output is correct |
4 |
Correct |
16 ms |
16760 KB |
Output is correct |
5 |
Correct |
16 ms |
16760 KB |
Output is correct |
6 |
Correct |
16 ms |
16888 KB |
Output is correct |
7 |
Correct |
16 ms |
16888 KB |
Output is correct |
8 |
Correct |
18 ms |
16888 KB |
Output is correct |
9 |
Correct |
16 ms |
16888 KB |
Output is correct |
10 |
Correct |
16 ms |
16888 KB |
Output is correct |
11 |
Correct |
16 ms |
16888 KB |
Output is correct |
12 |
Correct |
17 ms |
16888 KB |
Output is correct |
13 |
Correct |
16 ms |
16888 KB |
Output is correct |
14 |
Correct |
18 ms |
16888 KB |
Output is correct |
15 |
Correct |
16 ms |
16888 KB |
Output is correct |
16 |
Correct |
16 ms |
16892 KB |
Output is correct |
17 |
Correct |
17 ms |
16888 KB |
Output is correct |
18 |
Correct |
19 ms |
16888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16760 KB |
Output is correct |
2 |
Correct |
16 ms |
16760 KB |
Output is correct |
3 |
Correct |
16 ms |
16760 KB |
Output is correct |
4 |
Correct |
16 ms |
16760 KB |
Output is correct |
5 |
Correct |
16 ms |
16760 KB |
Output is correct |
6 |
Correct |
16 ms |
16888 KB |
Output is correct |
7 |
Correct |
16 ms |
16888 KB |
Output is correct |
8 |
Correct |
18 ms |
16888 KB |
Output is correct |
9 |
Correct |
16 ms |
16888 KB |
Output is correct |
10 |
Correct |
16 ms |
16888 KB |
Output is correct |
11 |
Correct |
16 ms |
16888 KB |
Output is correct |
12 |
Correct |
17 ms |
16888 KB |
Output is correct |
13 |
Correct |
16 ms |
16888 KB |
Output is correct |
14 |
Correct |
18 ms |
16888 KB |
Output is correct |
15 |
Correct |
16 ms |
16888 KB |
Output is correct |
16 |
Correct |
16 ms |
16892 KB |
Output is correct |
17 |
Correct |
17 ms |
16888 KB |
Output is correct |
18 |
Correct |
19 ms |
16888 KB |
Output is correct |
19 |
Correct |
55 ms |
18040 KB |
Output is correct |
20 |
Correct |
60 ms |
18040 KB |
Output is correct |
21 |
Correct |
60 ms |
18168 KB |
Output is correct |
22 |
Correct |
62 ms |
18552 KB |
Output is correct |
23 |
Correct |
101 ms |
23288 KB |
Output is correct |
24 |
Correct |
129 ms |
24700 KB |
Output is correct |
25 |
Correct |
150 ms |
25592 KB |
Output is correct |
26 |
Correct |
144 ms |
26872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16888 KB |
Output is correct |
2 |
Correct |
18 ms |
16760 KB |
Output is correct |
3 |
Correct |
22 ms |
16760 KB |
Output is correct |
4 |
Correct |
70 ms |
16888 KB |
Output is correct |
5 |
Correct |
277 ms |
17272 KB |
Output is correct |
6 |
Correct |
15 ms |
16808 KB |
Output is correct |
7 |
Correct |
16 ms |
17144 KB |
Output is correct |
8 |
Correct |
18 ms |
17144 KB |
Output is correct |
9 |
Correct |
23 ms |
17144 KB |
Output is correct |
10 |
Correct |
76 ms |
17148 KB |
Output is correct |
11 |
Correct |
302 ms |
17784 KB |
Output is correct |
12 |
Correct |
28 ms |
19708 KB |
Output is correct |
13 |
Correct |
30 ms |
19708 KB |
Output is correct |
14 |
Correct |
34 ms |
19704 KB |
Output is correct |
15 |
Correct |
88 ms |
19832 KB |
Output is correct |
16 |
Correct |
332 ms |
20344 KB |
Output is correct |
17 |
Correct |
389 ms |
75156 KB |
Output is correct |
18 |
Correct |
403 ms |
75152 KB |
Output is correct |
19 |
Correct |
416 ms |
75156 KB |
Output is correct |
20 |
Correct |
515 ms |
75276 KB |
Output is correct |
21 |
Correct |
1065 ms |
75792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
18296 KB |
Output is correct |
2 |
Correct |
75 ms |
18296 KB |
Output is correct |
3 |
Correct |
296 ms |
18552 KB |
Output is correct |
4 |
Correct |
565 ms |
18916 KB |
Output is correct |
5 |
Correct |
110 ms |
36216 KB |
Output is correct |
6 |
Correct |
215 ms |
36216 KB |
Output is correct |
7 |
Correct |
667 ms |
36560 KB |
Output is correct |
8 |
Correct |
1231 ms |
36728 KB |
Output is correct |
9 |
Correct |
600 ms |
129244 KB |
Output is correct |
10 |
Correct |
785 ms |
129244 KB |
Output is correct |
11 |
Correct |
1657 ms |
129500 KB |
Output is correct |
12 |
Correct |
2660 ms |
130012 KB |
Output is correct |
13 |
Correct |
1290 ms |
255040 KB |
Output is correct |
14 |
Correct |
1515 ms |
255052 KB |
Output is correct |
15 |
Correct |
2579 ms |
255364 KB |
Output is correct |
16 |
Correct |
3891 ms |
255572 KB |
Output is correct |
17 |
Execution timed out |
5083 ms |
255676 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5084 ms |
203196 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16760 KB |
Output is correct |
2 |
Correct |
16 ms |
16760 KB |
Output is correct |
3 |
Correct |
16 ms |
16760 KB |
Output is correct |
4 |
Correct |
16 ms |
16760 KB |
Output is correct |
5 |
Correct |
16 ms |
16760 KB |
Output is correct |
6 |
Correct |
16 ms |
16888 KB |
Output is correct |
7 |
Correct |
16 ms |
16888 KB |
Output is correct |
8 |
Correct |
18 ms |
16888 KB |
Output is correct |
9 |
Correct |
16 ms |
16888 KB |
Output is correct |
10 |
Correct |
16 ms |
16888 KB |
Output is correct |
11 |
Correct |
16 ms |
16888 KB |
Output is correct |
12 |
Correct |
17 ms |
16888 KB |
Output is correct |
13 |
Correct |
16 ms |
16888 KB |
Output is correct |
14 |
Correct |
18 ms |
16888 KB |
Output is correct |
15 |
Correct |
16 ms |
16888 KB |
Output is correct |
16 |
Correct |
16 ms |
16892 KB |
Output is correct |
17 |
Correct |
17 ms |
16888 KB |
Output is correct |
18 |
Correct |
19 ms |
16888 KB |
Output is correct |
19 |
Correct |
55 ms |
18040 KB |
Output is correct |
20 |
Correct |
60 ms |
18040 KB |
Output is correct |
21 |
Correct |
60 ms |
18168 KB |
Output is correct |
22 |
Correct |
62 ms |
18552 KB |
Output is correct |
23 |
Correct |
101 ms |
23288 KB |
Output is correct |
24 |
Correct |
129 ms |
24700 KB |
Output is correct |
25 |
Correct |
150 ms |
25592 KB |
Output is correct |
26 |
Correct |
144 ms |
26872 KB |
Output is correct |
27 |
Correct |
15 ms |
16888 KB |
Output is correct |
28 |
Correct |
18 ms |
16760 KB |
Output is correct |
29 |
Correct |
22 ms |
16760 KB |
Output is correct |
30 |
Correct |
70 ms |
16888 KB |
Output is correct |
31 |
Correct |
277 ms |
17272 KB |
Output is correct |
32 |
Correct |
15 ms |
16808 KB |
Output is correct |
33 |
Correct |
16 ms |
17144 KB |
Output is correct |
34 |
Correct |
18 ms |
17144 KB |
Output is correct |
35 |
Correct |
23 ms |
17144 KB |
Output is correct |
36 |
Correct |
76 ms |
17148 KB |
Output is correct |
37 |
Correct |
302 ms |
17784 KB |
Output is correct |
38 |
Correct |
28 ms |
19708 KB |
Output is correct |
39 |
Correct |
30 ms |
19708 KB |
Output is correct |
40 |
Correct |
34 ms |
19704 KB |
Output is correct |
41 |
Correct |
88 ms |
19832 KB |
Output is correct |
42 |
Correct |
332 ms |
20344 KB |
Output is correct |
43 |
Correct |
389 ms |
75156 KB |
Output is correct |
44 |
Correct |
403 ms |
75152 KB |
Output is correct |
45 |
Correct |
416 ms |
75156 KB |
Output is correct |
46 |
Correct |
515 ms |
75276 KB |
Output is correct |
47 |
Correct |
1065 ms |
75792 KB |
Output is correct |
48 |
Correct |
26 ms |
18296 KB |
Output is correct |
49 |
Correct |
75 ms |
18296 KB |
Output is correct |
50 |
Correct |
296 ms |
18552 KB |
Output is correct |
51 |
Correct |
565 ms |
18916 KB |
Output is correct |
52 |
Correct |
110 ms |
36216 KB |
Output is correct |
53 |
Correct |
215 ms |
36216 KB |
Output is correct |
54 |
Correct |
667 ms |
36560 KB |
Output is correct |
55 |
Correct |
1231 ms |
36728 KB |
Output is correct |
56 |
Correct |
600 ms |
129244 KB |
Output is correct |
57 |
Correct |
785 ms |
129244 KB |
Output is correct |
58 |
Correct |
1657 ms |
129500 KB |
Output is correct |
59 |
Correct |
2660 ms |
130012 KB |
Output is correct |
60 |
Correct |
1290 ms |
255040 KB |
Output is correct |
61 |
Correct |
1515 ms |
255052 KB |
Output is correct |
62 |
Correct |
2579 ms |
255364 KB |
Output is correct |
63 |
Correct |
3891 ms |
255572 KB |
Output is correct |
64 |
Execution timed out |
5083 ms |
255676 KB |
Time limit exceeded |