#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
struct SegmentTree {
int lv;
ll d[270007], ins[270007];
SegmentTree(int n = 100000) {
lv = 2;
while(lv < n + 2)
lv *= 2;
}
void insert(int a, int b, int l, int r, int w, ll x) {
if(b < l || a > r || l > r)
return ;
if(a <= l && r <= b) {
d[w] += x;
ins[w] += x;
return ;
}
insert(a, b, l, (l + r) / 2, 2 * w, x);
insert(a, b, (l + r) / 2 + 1, r, 2 * w + 1, x);
d[w] = max(d[2 * w], d[2 * w + 1]) + ins[w];
}
void insert(int a, int b, ll x) {
insert(a, b, 0, lv - 1, 1, x);
}
ll query(int a, int b, int l, int r, int w) {
if(b < l || a > r || l > r)
return 0;
if(a <= l && r <= b)
return d[w];
ll p1 = query(a, b, l, (l + r) / 2, 2 * w);
ll p2 = query(a, b, (l + r) / 2 + 1, r, 2 * w + 1);
return max(p1, p2) + ins[w];
}
ll query(int a, int b) {
return query(a, b, 0, lv - 1, 1);
}
void initv(int i, ll x) {
d[lv + i] = x;
}
void process_init() {
for(int i = lv - 1 ; i >= 1 ; i--)
d[i] = max(d[2 * i], d[2 * i + 1]);
}
};
int n, q;
ll w;
vector<pll> G[100007];
bool del[100007];
int innum[20][100007], outnum[20][100007];
int nxtnum[20];
int h[100007];
int vis[100007], viscnt;
int centro, total;
int sz[100007];
vector<int> ch[100007];
set<pll, greater<pll> > S[100007];
set<pll, greater<pll> > global;
ll globald[100007];
int p[100007];
SegmentTree ST[20];
ii E[100007];
ll ecost[100007];
ll prevv[20][100007];
void dfs(int w) {
sz[w] = 1;
vis[w] = viscnt;
for(auto p : G[w]) {
if(!del[p.X] && vis[p.X] != viscnt) {
dfs(p.X);
sz[w] += sz[p.X];
}
}
}
void dfs2(int w) {
int maxsz = 0;
vis[w] = viscnt;
for(auto p : G[w]) {
if(!del[p.X] && vis[p.X] != viscnt) {
dfs2(p.X);
maxsz = max(maxsz, sz[p.X]);
}
}
maxsz = max(maxsz, total - sz[w]);
if(maxsz <= total / 2)
centro = w;
}
void dfs3(int w, int lvl, ll dist = 0) {
innum[lvl][w] = outnum[lvl][w] = nxtnum[lvl]++;
vis[w] = viscnt;
ST[lvl].initv(innum[lvl][w], dist);
for(auto p : G[w]) {
if(!del[p.X] && vis[p.X] != viscnt) {
dfs3(p.X, lvl, dist + p.Y);
outnum[lvl][w] = max(outnum[lvl][w], outnum[lvl][p.X]);
}
}
}
int build(int w, int lvl) {
viscnt++;
dfs(w);
total = sz[w];
viscnt++;
dfs2(w);
int c = centro;
h[c] = lvl;
viscnt++;
dfs3(c, lvl);
del[c] = 1;
for(auto p : G[c]) {
if(!del[p.X]) {
ch[c].push_back(p.X);
::p[build(p.X, lvl + 1)] = c;
}
}
return c;
}
void upd_global(int w) {
ll d = 0;
if(S[w].size() >= 1)
d += S[w].begin()->X;
if(S[w].size() >= 2)
d += next(S[w].begin())->X;
global.erase({globald[w], w});
globald[w] = d;
global.insert({globald[w], w});
}
ll get_answer() {
if(global.empty())
return 0;
return global.begin()->X;
}
void update(int e, ll x) {
ll delta = x - ecost[e];
ecost[e] = x;
int c;
if(h[E[e].X] < h[E[e].Y])
c = E[e].X;
else
c = E[e].Y;
//~ cout << "c= "<< c << endl;
while(c) {
int w;
if(innum[h[c]][E[e].X] > innum[h[c]][E[e].Y])
w = E[e].X;
else
w = E[e].Y;
int pocz = 0, kon = ch[c].size() - 1, mid;
while(pocz < kon) {
mid = (pocz + kon) / 2;
if(outnum[h[c]][ch[c][mid]] >= innum[h[c]][w])
kon = mid;
else
pocz = mid + 1;
}
int u = ch[c][pocz];
//~ cout << w << " "<< u << endl;
ll prevv = ::prevv[h[c]][u];
if(prevv == -1)
prevv = ST[h[c]].query(innum[h[c]][u], outnum[h[c]][u]);
S[c].erase({prevv, u});
ST[h[c]].insert(innum[h[c]][w], outnum[h[c]][w], delta);
ll newv = ST[h[c]].query(innum[h[c]][u], outnum[h[c]][u]);
S[c].insert({newv, u});
::prevv[h[c]][u] = newv;
upd_global(c);
c = p[c];
}
//~ cout << "global: ";
//~ for(auto p : global)
//~ cout << "(" << p.X << ", " << p.Y << ") ";
//~ cout << endl;
//~ cout << "S[10]: ";
//~ for(auto p : S[10])
//~ cout << "(" << p.X << ", " << p.Y << ") ";
//~ cout << endl;
}
int main() {
memset(prevv, -1, sizeof prevv);
scanf("%d%d%lld", &n, &q, &w);
for(int i = 1 ; i < n ; i++) {
int a, b;
ll c;
scanf("%d%d%lld", &a, &b, &c);
G[a].emplace_back(b, c);
G[b].emplace_back(a, c);
E[i] = {a, b};
ecost[i] = c;
}
build(1, 0);
//~ for(int i = 1 ; i <= n ; i++)
//~ cout << i << " " << p[i] << endl;
for(int i = 0 ; i < 20 ; i++)
ST[i].process_init();
for(int i = 1 ; i <= n ; i++) {
for(int j : ch[i])
S[i].insert({ST[h[i]].query(innum[h[i]][j], outnum[h[i]][j]), j});
upd_global(i);
}
ll last = 0;
while(q--) {
ll d, e;
scanf("%lld%lld", &d, &e);
d = (d + last) % (n - 1);
e = (e + last) % w;
update(d + 1, e);
last = get_answer();
printf("%lld\n", last);
}
return 0;
}
Compilation message
diameter.cpp: In function 'int main()':
diameter.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &n, &q, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:247:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &d, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
46208 KB |
Output is correct |
2 |
Correct |
30 ms |
46208 KB |
Output is correct |
3 |
Correct |
30 ms |
46208 KB |
Output is correct |
4 |
Correct |
29 ms |
46328 KB |
Output is correct |
5 |
Correct |
30 ms |
46336 KB |
Output is correct |
6 |
Correct |
29 ms |
46200 KB |
Output is correct |
7 |
Correct |
30 ms |
46204 KB |
Output is correct |
8 |
Correct |
30 ms |
46200 KB |
Output is correct |
9 |
Correct |
29 ms |
46204 KB |
Output is correct |
10 |
Correct |
30 ms |
46208 KB |
Output is correct |
11 |
Correct |
29 ms |
46208 KB |
Output is correct |
12 |
Correct |
30 ms |
46208 KB |
Output is correct |
13 |
Correct |
30 ms |
46328 KB |
Output is correct |
14 |
Correct |
30 ms |
46328 KB |
Output is correct |
15 |
Correct |
30 ms |
46328 KB |
Output is correct |
16 |
Correct |
30 ms |
46328 KB |
Output is correct |
17 |
Correct |
30 ms |
46328 KB |
Output is correct |
18 |
Correct |
32 ms |
46336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
46208 KB |
Output is correct |
2 |
Correct |
30 ms |
46208 KB |
Output is correct |
3 |
Correct |
30 ms |
46208 KB |
Output is correct |
4 |
Correct |
29 ms |
46328 KB |
Output is correct |
5 |
Correct |
30 ms |
46336 KB |
Output is correct |
6 |
Correct |
29 ms |
46200 KB |
Output is correct |
7 |
Correct |
30 ms |
46204 KB |
Output is correct |
8 |
Correct |
30 ms |
46200 KB |
Output is correct |
9 |
Correct |
29 ms |
46204 KB |
Output is correct |
10 |
Correct |
30 ms |
46208 KB |
Output is correct |
11 |
Correct |
29 ms |
46208 KB |
Output is correct |
12 |
Correct |
30 ms |
46208 KB |
Output is correct |
13 |
Correct |
30 ms |
46328 KB |
Output is correct |
14 |
Correct |
30 ms |
46328 KB |
Output is correct |
15 |
Correct |
30 ms |
46328 KB |
Output is correct |
16 |
Correct |
30 ms |
46328 KB |
Output is correct |
17 |
Correct |
30 ms |
46328 KB |
Output is correct |
18 |
Correct |
32 ms |
46336 KB |
Output is correct |
19 |
Correct |
60 ms |
46900 KB |
Output is correct |
20 |
Correct |
57 ms |
46968 KB |
Output is correct |
21 |
Correct |
62 ms |
46976 KB |
Output is correct |
22 |
Correct |
69 ms |
46972 KB |
Output is correct |
23 |
Correct |
79 ms |
49016 KB |
Output is correct |
24 |
Correct |
87 ms |
49272 KB |
Output is correct |
25 |
Correct |
90 ms |
49528 KB |
Output is correct |
26 |
Correct |
104 ms |
49912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
46200 KB |
Output is correct |
2 |
Correct |
32 ms |
46208 KB |
Output is correct |
3 |
Correct |
31 ms |
46200 KB |
Output is correct |
4 |
Correct |
50 ms |
46328 KB |
Output is correct |
5 |
Correct |
132 ms |
47332 KB |
Output is correct |
6 |
Correct |
29 ms |
46200 KB |
Output is correct |
7 |
Correct |
30 ms |
46336 KB |
Output is correct |
8 |
Correct |
29 ms |
46336 KB |
Output is correct |
9 |
Correct |
34 ms |
46372 KB |
Output is correct |
10 |
Correct |
56 ms |
46584 KB |
Output is correct |
11 |
Correct |
158 ms |
47608 KB |
Output is correct |
12 |
Correct |
35 ms |
47480 KB |
Output is correct |
13 |
Correct |
35 ms |
47480 KB |
Output is correct |
14 |
Correct |
45 ms |
47608 KB |
Output is correct |
15 |
Correct |
67 ms |
47744 KB |
Output is correct |
16 |
Correct |
201 ms |
49016 KB |
Output is correct |
17 |
Correct |
186 ms |
72164 KB |
Output is correct |
18 |
Correct |
183 ms |
72420 KB |
Output is correct |
19 |
Correct |
195 ms |
72932 KB |
Output is correct |
20 |
Correct |
238 ms |
73188 KB |
Output is correct |
21 |
Correct |
560 ms |
74732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
46968 KB |
Output is correct |
2 |
Correct |
72 ms |
46968 KB |
Output is correct |
3 |
Correct |
256 ms |
47580 KB |
Output is correct |
4 |
Correct |
461 ms |
48248 KB |
Output is correct |
5 |
Correct |
54 ms |
52472 KB |
Output is correct |
6 |
Correct |
114 ms |
52600 KB |
Output is correct |
7 |
Correct |
380 ms |
53240 KB |
Output is correct |
8 |
Correct |
742 ms |
54012 KB |
Output is correct |
9 |
Correct |
136 ms |
79480 KB |
Output is correct |
10 |
Correct |
236 ms |
79840 KB |
Output is correct |
11 |
Correct |
691 ms |
80572 KB |
Output is correct |
12 |
Correct |
1248 ms |
81400 KB |
Output is correct |
13 |
Correct |
244 ms |
112632 KB |
Output is correct |
14 |
Correct |
363 ms |
115960 KB |
Output is correct |
15 |
Correct |
969 ms |
116856 KB |
Output is correct |
16 |
Correct |
1690 ms |
117584 KB |
Output is correct |
17 |
Correct |
3304 ms |
107128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2807 ms |
112080 KB |
Output is correct |
2 |
Correct |
3007 ms |
113516 KB |
Output is correct |
3 |
Correct |
2784 ms |
112376 KB |
Output is correct |
4 |
Correct |
2872 ms |
113400 KB |
Output is correct |
5 |
Correct |
2843 ms |
110464 KB |
Output is correct |
6 |
Correct |
2576 ms |
100968 KB |
Output is correct |
7 |
Correct |
3967 ms |
123760 KB |
Output is correct |
8 |
Correct |
4243 ms |
123964 KB |
Output is correct |
9 |
Correct |
4019 ms |
123904 KB |
Output is correct |
10 |
Correct |
4042 ms |
123880 KB |
Output is correct |
11 |
Correct |
3977 ms |
120852 KB |
Output is correct |
12 |
Correct |
3660 ms |
108020 KB |
Output is correct |
13 |
Correct |
4347 ms |
130196 KB |
Output is correct |
14 |
Correct |
4484 ms |
130224 KB |
Output is correct |
15 |
Correct |
4537 ms |
130152 KB |
Output is correct |
16 |
Correct |
4414 ms |
130112 KB |
Output is correct |
17 |
Correct |
4190 ms |
126348 KB |
Output is correct |
18 |
Correct |
3945 ms |
110292 KB |
Output is correct |
19 |
Correct |
4296 ms |
130148 KB |
Output is correct |
20 |
Correct |
4696 ms |
130252 KB |
Output is correct |
21 |
Correct |
4425 ms |
130240 KB |
Output is correct |
22 |
Correct |
4325 ms |
129916 KB |
Output is correct |
23 |
Correct |
4151 ms |
126316 KB |
Output is correct |
24 |
Correct |
3917 ms |
110188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
46208 KB |
Output is correct |
2 |
Correct |
30 ms |
46208 KB |
Output is correct |
3 |
Correct |
30 ms |
46208 KB |
Output is correct |
4 |
Correct |
29 ms |
46328 KB |
Output is correct |
5 |
Correct |
30 ms |
46336 KB |
Output is correct |
6 |
Correct |
29 ms |
46200 KB |
Output is correct |
7 |
Correct |
30 ms |
46204 KB |
Output is correct |
8 |
Correct |
30 ms |
46200 KB |
Output is correct |
9 |
Correct |
29 ms |
46204 KB |
Output is correct |
10 |
Correct |
30 ms |
46208 KB |
Output is correct |
11 |
Correct |
29 ms |
46208 KB |
Output is correct |
12 |
Correct |
30 ms |
46208 KB |
Output is correct |
13 |
Correct |
30 ms |
46328 KB |
Output is correct |
14 |
Correct |
30 ms |
46328 KB |
Output is correct |
15 |
Correct |
30 ms |
46328 KB |
Output is correct |
16 |
Correct |
30 ms |
46328 KB |
Output is correct |
17 |
Correct |
30 ms |
46328 KB |
Output is correct |
18 |
Correct |
32 ms |
46336 KB |
Output is correct |
19 |
Correct |
60 ms |
46900 KB |
Output is correct |
20 |
Correct |
57 ms |
46968 KB |
Output is correct |
21 |
Correct |
62 ms |
46976 KB |
Output is correct |
22 |
Correct |
69 ms |
46972 KB |
Output is correct |
23 |
Correct |
79 ms |
49016 KB |
Output is correct |
24 |
Correct |
87 ms |
49272 KB |
Output is correct |
25 |
Correct |
90 ms |
49528 KB |
Output is correct |
26 |
Correct |
104 ms |
49912 KB |
Output is correct |
27 |
Correct |
29 ms |
46200 KB |
Output is correct |
28 |
Correct |
32 ms |
46208 KB |
Output is correct |
29 |
Correct |
31 ms |
46200 KB |
Output is correct |
30 |
Correct |
50 ms |
46328 KB |
Output is correct |
31 |
Correct |
132 ms |
47332 KB |
Output is correct |
32 |
Correct |
29 ms |
46200 KB |
Output is correct |
33 |
Correct |
30 ms |
46336 KB |
Output is correct |
34 |
Correct |
29 ms |
46336 KB |
Output is correct |
35 |
Correct |
34 ms |
46372 KB |
Output is correct |
36 |
Correct |
56 ms |
46584 KB |
Output is correct |
37 |
Correct |
158 ms |
47608 KB |
Output is correct |
38 |
Correct |
35 ms |
47480 KB |
Output is correct |
39 |
Correct |
35 ms |
47480 KB |
Output is correct |
40 |
Correct |
45 ms |
47608 KB |
Output is correct |
41 |
Correct |
67 ms |
47744 KB |
Output is correct |
42 |
Correct |
201 ms |
49016 KB |
Output is correct |
43 |
Correct |
186 ms |
72164 KB |
Output is correct |
44 |
Correct |
183 ms |
72420 KB |
Output is correct |
45 |
Correct |
195 ms |
72932 KB |
Output is correct |
46 |
Correct |
238 ms |
73188 KB |
Output is correct |
47 |
Correct |
560 ms |
74732 KB |
Output is correct |
48 |
Correct |
34 ms |
46968 KB |
Output is correct |
49 |
Correct |
72 ms |
46968 KB |
Output is correct |
50 |
Correct |
256 ms |
47580 KB |
Output is correct |
51 |
Correct |
461 ms |
48248 KB |
Output is correct |
52 |
Correct |
54 ms |
52472 KB |
Output is correct |
53 |
Correct |
114 ms |
52600 KB |
Output is correct |
54 |
Correct |
380 ms |
53240 KB |
Output is correct |
55 |
Correct |
742 ms |
54012 KB |
Output is correct |
56 |
Correct |
136 ms |
79480 KB |
Output is correct |
57 |
Correct |
236 ms |
79840 KB |
Output is correct |
58 |
Correct |
691 ms |
80572 KB |
Output is correct |
59 |
Correct |
1248 ms |
81400 KB |
Output is correct |
60 |
Correct |
244 ms |
112632 KB |
Output is correct |
61 |
Correct |
363 ms |
115960 KB |
Output is correct |
62 |
Correct |
969 ms |
116856 KB |
Output is correct |
63 |
Correct |
1690 ms |
117584 KB |
Output is correct |
64 |
Correct |
3304 ms |
107128 KB |
Output is correct |
65 |
Correct |
2807 ms |
112080 KB |
Output is correct |
66 |
Correct |
3007 ms |
113516 KB |
Output is correct |
67 |
Correct |
2784 ms |
112376 KB |
Output is correct |
68 |
Correct |
2872 ms |
113400 KB |
Output is correct |
69 |
Correct |
2843 ms |
110464 KB |
Output is correct |
70 |
Correct |
2576 ms |
100968 KB |
Output is correct |
71 |
Correct |
3967 ms |
123760 KB |
Output is correct |
72 |
Correct |
4243 ms |
123964 KB |
Output is correct |
73 |
Correct |
4019 ms |
123904 KB |
Output is correct |
74 |
Correct |
4042 ms |
123880 KB |
Output is correct |
75 |
Correct |
3977 ms |
120852 KB |
Output is correct |
76 |
Correct |
3660 ms |
108020 KB |
Output is correct |
77 |
Correct |
4347 ms |
130196 KB |
Output is correct |
78 |
Correct |
4484 ms |
130224 KB |
Output is correct |
79 |
Correct |
4537 ms |
130152 KB |
Output is correct |
80 |
Correct |
4414 ms |
130112 KB |
Output is correct |
81 |
Correct |
4190 ms |
126348 KB |
Output is correct |
82 |
Correct |
3945 ms |
110292 KB |
Output is correct |
83 |
Correct |
4296 ms |
130148 KB |
Output is correct |
84 |
Correct |
4696 ms |
130252 KB |
Output is correct |
85 |
Correct |
4425 ms |
130240 KB |
Output is correct |
86 |
Correct |
4325 ms |
129916 KB |
Output is correct |
87 |
Correct |
4151 ms |
126316 KB |
Output is correct |
88 |
Correct |
3917 ms |
110188 KB |
Output is correct |
89 |
Correct |
2818 ms |
111948 KB |
Output is correct |
90 |
Correct |
3338 ms |
116728 KB |
Output is correct |
91 |
Correct |
3852 ms |
121464 KB |
Output is correct |
92 |
Correct |
3900 ms |
123000 KB |
Output is correct |
93 |
Correct |
4093 ms |
125432 KB |
Output is correct |
94 |
Correct |
4119 ms |
126200 KB |
Output is correct |
95 |
Correct |
4329 ms |
127744 KB |
Output is correct |
96 |
Correct |
4300 ms |
127096 KB |
Output is correct |
97 |
Correct |
4380 ms |
127480 KB |
Output is correct |
98 |
Correct |
4411 ms |
129400 KB |
Output is correct |
99 |
Correct |
4678 ms |
127352 KB |
Output is correct |
100 |
Correct |
4507 ms |
127224 KB |
Output is correct |