#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll seg[4000000];
ll lazy[4000000];
ll maxn = 1000000-1;
void push(ll v){
seg[2*v] += lazy[v];
seg[2*v+1] += lazy[v];
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
lazy[v] = 0;
}
void upd(ll v, ll tl, ll tr, ll l, ll r, ll val){
if(r < tl || tr < l)
return;
if(l <= tl && tr <= r){
seg[v] += val;
lazy[v] += val;
}
else{
push(v);
upd(2*v, tl, (tl+tr)/2, l, r, val);
upd(2*v+1, (tl+tr)/2+1, tr, l, r, val);
seg[v] = max(seg[2*v], seg[2*v+1]);
}
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
if(r < tl || tr < l)
return -1e18;
if(l <= tl && tr <= r){
return seg[v];
}
else{
push(v);
return max(
get(2*v, tl, (tl+tr)/2, l, r),
get(2*v+1, (tl+tr)/2+1, tr, l, r));
}
}
struct edge{
ll x, y, z;
};
vector<pll> g[100009];
edge e[100009];
ll sz[100009];
ll block[100009];
void findsz(ll v, ll prt){
sz[v] = 1;
for(auto u : g[v]){
if(block[u.ff] || u.ff == prt) continue;
findsz(u.ff, v);
sz[v] += sz[u.ff];
}
}
ll findcentroid(ll v, ll prt, ll totsz){
for(auto u : g[v]){
if(block[u.ff] || u.ff == prt) continue;
if(sz[u.ff]*2 > totsz)
return findcentroid(u.ff, v, totsz);
}
return v;
}
ll curtime = 0;
ll root;
unordered_map<ll, ll> tin[100009];
unordered_map<ll, ll> tout[100009];
vector<ll> change[100009];
vector<pll> entry[100009];
multiset<ll, greater<ll>> centmax[100009];
ll centans[100009];
multiset<ll, greater<ll>> totmax;
void dfs(ll v, ll prt){
tin[root][v] = curtime++;
ll distoprt;
for(auto u : g[v]){
if(block[u.ff])
continue;
if(u.ff == prt){
change[u.ss].pb(root);
distoprt = e[u.ss].z;
continue;
}
dfs(u.ff, v);
}
tout[root][v] = curtime-1;
upd(1, 0, maxn, tin[root][v], tout[root][v], distoprt);
}
void decomp(){
findsz(root, 0);
root = findcentroid(root, 0, sz[root]);
tin[root][root] = -1;
for(auto u : g[root]){
if(block[u.ff]) continue;
dfs(u.ff, root);
entry[root].pb({tin[root][u.ff], tout[root][u.ff]});
centmax[root].insert(get(1, 0, maxn, tin[root][u.ff], tout[root][u.ff]));
}
if(centmax[root].empty()) return;
auto it = centmax[root].begin();
centans[root] = *it;
if(centmax[root].size() >= 2){
++it;
centans[root] += *it;
}
totmax.insert(centans[root]);
block[root] = 1;
ll v = root;
for(auto u : g[v]){
if(block[u.ff]) continue;
root = u.ff;
decomp();
}
}
ll n, q, w;
ll last = 0;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> q >> w;
for(ll i = 0; i < n-1; ++i){
cin >> e[i].x >> e[i].y >> e[i].z;
g[e[i].x].pb({e[i].y, i});
g[e[i].y].pb({e[i].x, i});
}
root = 1;
decomp();
assert(curtime <= maxn);
for(ll i = 0; i < q; ++i){
ll d, val;
cin >> d >> val;
d = (d+last)%(n-1);
val = (val+last)%w;
ll ch = val - e[d].z;
for(auto root : change[d]){
ll v;
if(tin[root][e[d].x] > tin[root][e[d].y])
v = e[d].x;
else
v = e[d].y;
ll in = tin[root][v];
ll out = tout[root][v];
pii cursub = entry[root][upper_bound(all(entry[root]), mp(in, (ll)1e18))-entry[root].begin()-1];
centmax[root].erase(centmax[root].lower_bound(get(1, 0, maxn, cursub.ff, cursub.ss)));
upd(1, 0, maxn, in, out, ch);
centmax[root].insert(get(1, 0, maxn, cursub.ff, cursub.ss));
totmax.erase(totmax.lower_bound(centans[root]));
auto it = centmax[root].begin();
centans[root] = *it;
if(centmax[root].size() >= 2){
++it;
centans[root] += *it;
}
totmax.insert(centans[root]);
}
last = *totmax.begin();
cout << last << '\n';
e[d].z = val;
}
}
Compilation message
diameter.cpp: In function 'void dfs(ll, ll)':
diameter.cpp:99:8: warning: 'distoprt' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | upd(1, 0, maxn, tin[root][v], tout[root][v], distoprt);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23168 KB |
Output is correct |
2 |
Correct |
16 ms |
23168 KB |
Output is correct |
3 |
Correct |
17 ms |
23168 KB |
Output is correct |
4 |
Correct |
17 ms |
23168 KB |
Output is correct |
5 |
Correct |
17 ms |
23176 KB |
Output is correct |
6 |
Correct |
17 ms |
23168 KB |
Output is correct |
7 |
Correct |
17 ms |
23168 KB |
Output is correct |
8 |
Correct |
18 ms |
23296 KB |
Output is correct |
9 |
Correct |
18 ms |
23168 KB |
Output is correct |
10 |
Correct |
17 ms |
23168 KB |
Output is correct |
11 |
Correct |
20 ms |
23168 KB |
Output is correct |
12 |
Correct |
18 ms |
23168 KB |
Output is correct |
13 |
Correct |
17 ms |
23296 KB |
Output is correct |
14 |
Correct |
17 ms |
23296 KB |
Output is correct |
15 |
Correct |
17 ms |
23296 KB |
Output is correct |
16 |
Correct |
17 ms |
23296 KB |
Output is correct |
17 |
Correct |
18 ms |
23332 KB |
Output is correct |
18 |
Correct |
19 ms |
23424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23168 KB |
Output is correct |
2 |
Correct |
16 ms |
23168 KB |
Output is correct |
3 |
Correct |
17 ms |
23168 KB |
Output is correct |
4 |
Correct |
17 ms |
23168 KB |
Output is correct |
5 |
Correct |
17 ms |
23176 KB |
Output is correct |
6 |
Correct |
17 ms |
23168 KB |
Output is correct |
7 |
Correct |
17 ms |
23168 KB |
Output is correct |
8 |
Correct |
18 ms |
23296 KB |
Output is correct |
9 |
Correct |
18 ms |
23168 KB |
Output is correct |
10 |
Correct |
17 ms |
23168 KB |
Output is correct |
11 |
Correct |
20 ms |
23168 KB |
Output is correct |
12 |
Correct |
18 ms |
23168 KB |
Output is correct |
13 |
Correct |
17 ms |
23296 KB |
Output is correct |
14 |
Correct |
17 ms |
23296 KB |
Output is correct |
15 |
Correct |
17 ms |
23296 KB |
Output is correct |
16 |
Correct |
17 ms |
23296 KB |
Output is correct |
17 |
Correct |
18 ms |
23332 KB |
Output is correct |
18 |
Correct |
19 ms |
23424 KB |
Output is correct |
19 |
Correct |
63 ms |
24184 KB |
Output is correct |
20 |
Correct |
69 ms |
24192 KB |
Output is correct |
21 |
Correct |
77 ms |
24312 KB |
Output is correct |
22 |
Correct |
95 ms |
24728 KB |
Output is correct |
23 |
Correct |
113 ms |
28280 KB |
Output is correct |
24 |
Correct |
149 ms |
29816 KB |
Output is correct |
25 |
Correct |
181 ms |
30456 KB |
Output is correct |
26 |
Correct |
217 ms |
31608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23168 KB |
Output is correct |
2 |
Correct |
19 ms |
23168 KB |
Output is correct |
3 |
Correct |
19 ms |
23168 KB |
Output is correct |
4 |
Correct |
44 ms |
23296 KB |
Output is correct |
5 |
Correct |
150 ms |
23660 KB |
Output is correct |
6 |
Correct |
16 ms |
23168 KB |
Output is correct |
7 |
Correct |
17 ms |
23424 KB |
Output is correct |
8 |
Correct |
18 ms |
23424 KB |
Output is correct |
9 |
Correct |
23 ms |
23424 KB |
Output is correct |
10 |
Correct |
50 ms |
23544 KB |
Output is correct |
11 |
Correct |
183 ms |
23928 KB |
Output is correct |
12 |
Correct |
26 ms |
24960 KB |
Output is correct |
13 |
Correct |
30 ms |
24960 KB |
Output is correct |
14 |
Correct |
33 ms |
24960 KB |
Output is correct |
15 |
Correct |
68 ms |
25080 KB |
Output is correct |
16 |
Correct |
221 ms |
25592 KB |
Output is correct |
17 |
Correct |
268 ms |
58212 KB |
Output is correct |
18 |
Correct |
272 ms |
58224 KB |
Output is correct |
19 |
Correct |
299 ms |
58172 KB |
Output is correct |
20 |
Correct |
359 ms |
58480 KB |
Output is correct |
21 |
Correct |
803 ms |
58828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
24388 KB |
Output is correct |
2 |
Correct |
118 ms |
24440 KB |
Output is correct |
3 |
Correct |
413 ms |
24696 KB |
Output is correct |
4 |
Correct |
790 ms |
25208 KB |
Output is correct |
5 |
Correct |
139 ms |
39800 KB |
Output is correct |
6 |
Correct |
286 ms |
39928 KB |
Output is correct |
7 |
Correct |
938 ms |
40080 KB |
Output is correct |
8 |
Correct |
1882 ms |
40524 KB |
Output is correct |
9 |
Correct |
769 ms |
120760 KB |
Output is correct |
10 |
Correct |
965 ms |
120884 KB |
Output is correct |
11 |
Correct |
2017 ms |
121196 KB |
Output is correct |
12 |
Correct |
3433 ms |
121520 KB |
Output is correct |
13 |
Runtime error |
1318 ms |
442832 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
5079 ms |
180196 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23168 KB |
Output is correct |
2 |
Correct |
16 ms |
23168 KB |
Output is correct |
3 |
Correct |
17 ms |
23168 KB |
Output is correct |
4 |
Correct |
17 ms |
23168 KB |
Output is correct |
5 |
Correct |
17 ms |
23176 KB |
Output is correct |
6 |
Correct |
17 ms |
23168 KB |
Output is correct |
7 |
Correct |
17 ms |
23168 KB |
Output is correct |
8 |
Correct |
18 ms |
23296 KB |
Output is correct |
9 |
Correct |
18 ms |
23168 KB |
Output is correct |
10 |
Correct |
17 ms |
23168 KB |
Output is correct |
11 |
Correct |
20 ms |
23168 KB |
Output is correct |
12 |
Correct |
18 ms |
23168 KB |
Output is correct |
13 |
Correct |
17 ms |
23296 KB |
Output is correct |
14 |
Correct |
17 ms |
23296 KB |
Output is correct |
15 |
Correct |
17 ms |
23296 KB |
Output is correct |
16 |
Correct |
17 ms |
23296 KB |
Output is correct |
17 |
Correct |
18 ms |
23332 KB |
Output is correct |
18 |
Correct |
19 ms |
23424 KB |
Output is correct |
19 |
Correct |
63 ms |
24184 KB |
Output is correct |
20 |
Correct |
69 ms |
24192 KB |
Output is correct |
21 |
Correct |
77 ms |
24312 KB |
Output is correct |
22 |
Correct |
95 ms |
24728 KB |
Output is correct |
23 |
Correct |
113 ms |
28280 KB |
Output is correct |
24 |
Correct |
149 ms |
29816 KB |
Output is correct |
25 |
Correct |
181 ms |
30456 KB |
Output is correct |
26 |
Correct |
217 ms |
31608 KB |
Output is correct |
27 |
Correct |
16 ms |
23168 KB |
Output is correct |
28 |
Correct |
19 ms |
23168 KB |
Output is correct |
29 |
Correct |
19 ms |
23168 KB |
Output is correct |
30 |
Correct |
44 ms |
23296 KB |
Output is correct |
31 |
Correct |
150 ms |
23660 KB |
Output is correct |
32 |
Correct |
16 ms |
23168 KB |
Output is correct |
33 |
Correct |
17 ms |
23424 KB |
Output is correct |
34 |
Correct |
18 ms |
23424 KB |
Output is correct |
35 |
Correct |
23 ms |
23424 KB |
Output is correct |
36 |
Correct |
50 ms |
23544 KB |
Output is correct |
37 |
Correct |
183 ms |
23928 KB |
Output is correct |
38 |
Correct |
26 ms |
24960 KB |
Output is correct |
39 |
Correct |
30 ms |
24960 KB |
Output is correct |
40 |
Correct |
33 ms |
24960 KB |
Output is correct |
41 |
Correct |
68 ms |
25080 KB |
Output is correct |
42 |
Correct |
221 ms |
25592 KB |
Output is correct |
43 |
Correct |
268 ms |
58212 KB |
Output is correct |
44 |
Correct |
272 ms |
58224 KB |
Output is correct |
45 |
Correct |
299 ms |
58172 KB |
Output is correct |
46 |
Correct |
359 ms |
58480 KB |
Output is correct |
47 |
Correct |
803 ms |
58828 KB |
Output is correct |
48 |
Correct |
32 ms |
24388 KB |
Output is correct |
49 |
Correct |
118 ms |
24440 KB |
Output is correct |
50 |
Correct |
413 ms |
24696 KB |
Output is correct |
51 |
Correct |
790 ms |
25208 KB |
Output is correct |
52 |
Correct |
139 ms |
39800 KB |
Output is correct |
53 |
Correct |
286 ms |
39928 KB |
Output is correct |
54 |
Correct |
938 ms |
40080 KB |
Output is correct |
55 |
Correct |
1882 ms |
40524 KB |
Output is correct |
56 |
Correct |
769 ms |
120760 KB |
Output is correct |
57 |
Correct |
965 ms |
120884 KB |
Output is correct |
58 |
Correct |
2017 ms |
121196 KB |
Output is correct |
59 |
Correct |
3433 ms |
121520 KB |
Output is correct |
60 |
Runtime error |
1318 ms |
442832 KB |
Execution killed with signal 11 |
61 |
Halted |
0 ms |
0 KB |
- |