// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
const int N = 1e5 + 5;
const int LOG = 18;
const int INF = 2e9 + 5;
vector<iii> vec;
vector<ii> lst[N];
int dist[N];
void solve_sub2(int n, int q, int w){
int last = 0;
while(q--){
int d, e; cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
vec[d].fi = e;
for(int i = 1; i <= n; ++i)lst[i].clear();
for(int i = 0; i < n - 1; ++i){
lst[vec[i].se.fi].pb(mp(vec[i].se.se, vec[i].fi));
lst[vec[i].se.se].pb(mp(vec[i].se.fi, vec[i].fi));
}
for(int i = 1; i <= n; ++i)dist[i] = INF;
queue<int> q;
q.push(1);
dist[1] = 0;
while(!q.empty()){
int cur = q.front(); q.pop();
for(int i = 0; i < lst[cur].size(); ++i){
int nx = lst[cur][i].fi;
int cs = dist[cur] + lst[cur][i].se;
if(cs < dist[nx]){
dist[nx] = cs;
q.push(nx);
}
}
}
ii maxdist = mp(-1, -1);
for(int i = 1; i <= n; ++i){
maxdist = max(maxdist, mp(dist[i], i));
}
for(int i = 1; i <= n; ++i)dist[i] = INF;
q.push(maxdist.se);
dist[maxdist.se] = 0;
while(!q.empty()){
int cur = q.front(); q.pop();
for(int i = 0; i < lst[cur].size(); ++i){
int nx = lst[cur][i].fi;
int cs = dist[cur] + lst[cur][i].se;
if(cs < dist[nx]){
dist[nx] = cs;
q.push(nx);
}
}
}
int ans = -1;
for(int i = 1; i <= n; ++i){
ans = max(ans, dist[i]);
}
last = ans;
cout << ans << '\n';
}
return;
}
map<int, int> mep;
void solve_sub3(int n, int q, int w){
int last = 0;
while(q--){
int d, e; cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
--mep[vec[d].fi];
if(mep[vec[d].fi] == 0)mep.erase(vec[d].fi);
++mep[e];
vec[d].fi = e;
auto it = mep.end();
--it;
int ans = it->fi;
if(it->se > 1)ans += it->fi;
else{
--it;
ans += it->fi;
}
last = ans;
cout << ans << '\n';
}
return;
}
int par[N];
int depth[N];
int cost[N];
int ar[N];
int lf[N], rg[N];
struct node{
ii mx1, mx2; int lz;
};
node st[4 * N];
node merge(node a, node b){
return {max(a.mx1, b.mx1), max(min(a.mx1, b.mx1), max(a.mx2, b.mx2)), 0};
}
void build(int idx, int l, int r){
if(l == r){
st[l] = {mp(ar[l], l), mp(-1, -1), 0};
return;
}
int m = (l + r)/2;
build(idx * 2, l, m);
build(idx * 2 + 1, m + 1, r);
st[idx] = merge(st[idx * 2], st[idx * 2 + 1]);
return;
}
void apply(int idx, int l, int r, int v){
st[idx].mx1.fi += v;
st[idx].mx2.fi += v;
st[idx].lz += v;
return;
}
void pushdown(int idx, int l, int r){
if(st[idx].lz == 0)return;
int m = (l + r)/2;
apply(idx * 2, l, m, st[idx].lz);
apply(idx * 2 + 1, m + 1, r, st[idx].lz);
st[idx].lz = 0;
return;
}
void upd(int idx, int l, int r, int x, int y, int v){
if(l > y || r < x)return;
if(l >= x && r <= y){
apply(idx, l, r, v);
return;
}
pushdown(idx, l, r);
int m = (l + r)/2;
upd(idx * 2, l, m, x, y, v);
upd(idx * 2 + 1, m + 1, r, x, y, v);
st[idx] = merge(st[idx * 2], st[idx * 2 + 1]);
return;
}
node get(int idx, int l, int r, int x, int y){
if(l > y || r < x)return {mp(-1, -1), mp(-1, -1), 0};
if(l >= x && r <= y)return st[idx];
pushdown(idx, l, r);
int m = (l + r)/2;
return merge(get(idx * 2, l, m, x, y), get(idx * 2 + 1, m + 1, r, x, y));
}
ii dfs(int idx, int p, int cur_sum){
par[idx] = p;
ar[idx] = cur_sum;
ii res = mp(INF, 0);
for(int i = 0; i < lst[idx].size(); ++i){
int nx = lst[idx][i].fi;
if(nx == p)continue;
cost[nx] = lst[idx][i].se;
depth[nx] = depth[idx] + 1;
ii cur = dfs(nx, idx, cur_sum + lst[idx][i].se);
res.fi = min(res.fi, cur.fi);
res.se = max(res.se, cur.se);
}
lf[idx] = res.fi; rg[idx] = res.se;
return res;
}
node rs[N];
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, q, w; cin >> n >> q >> w;
bool sub3 = true;
for(int i = 0; i < n - 1; ++i){
int a, b, c; cin >> a >> b >> c;
lst[a].pb(mp(b, c));
lst[b].pb(mp(a, c));
vec.pb(mp(c, mp(a, b)));
++mep[c];
if(a != 1 && b != 1)sub3 = false;
}
if(n <= 5000 && q <= 5000){
solve_sub2(n, q, w);
return 0;
}
if(sub3){
solve_sub3(n, q, w);
return 0;
}
mep.clear();
dfs(1, -1, 0);
int id_l = 0;
for(int i = 1; i <= n; ++i){
if(lst[i].size() == 1){
id_l = i;
break;
}
}
build(1, 1, n);
for(int i = 1; i < id_l; ++i){
rs[i] = get(1, 1, n, lf[i], rg[i]);
rs[i].mx1.fi -= ar[i];
rs[i].mx2.fi -= ar[i];
mep[rs[i].mx1.fi + rs[i].mx2.fi]++;
}
int last = 0;
while(q--){
int d, e; cin >> d >> e;
d = (d + last) % (n - 1);
e = (e + last) % w;
int x = vec[d].se.fi, y = vec[d].se.se;
if(depth[x] < depth[y])swap(x, y);
upd(1, 1, n, lf[x], rg[x], e - cost[x]);
node res;
if(par[x] != -1)res = get(1, 1, n, lf[par[x]], rg[par[x]]);
int idx = x;
while(par[idx] != -1){
idx = par[idx];
node last_rs = rs[idx];
int last_sum = rs[idx].mx1.fi + rs[idx].mx2.fi;
node cur = res;
cur.mx1.fi -= ar[idx];
cur.mx2.fi -= ar[idx];
vector<ii> vecs;
vecs.pb(cur.mx1); vecs.pb(cur.mx2);
vecs.pb(rs[idx].mx1); vecs.pb(rs[idx].mx2);
sort(vecs.begin(), vecs.end());
reverse(vecs.begin(), vecs.end());
rs[idx].mx1 = rs[idx].mx2 = mp(-1, -1);
for(int i = 0; i < vecs.size(); ++i){
if(i > 0 && vecs[i] == vecs[i - 1])continue;
if(rs[idx].mx1 == mp(-1, -1))rs[idx].mx1 = vecs[i];
else if(rs[idx].mx2 == mp(-1, -1))rs[idx].mx2 = vecs[i];
}
if(last_rs.mx1.fi != rs[idx].mx1.fi || last_rs.mx2.fi != rs[idx].mx2.fi){
mep[last_sum]--;
mep[rs[idx].mx1.fi + rs[idx].mx2.fi]++;
}
}
cost[x] = e;
vec[d].fi = e;
auto it = mep.end();
--it;
while(it->se == 0){
mep.erase(it->fi);
--it;
}
int ans = it->fi;
if(it->se > 1){
ans += it->fi;
}else{
while(it->se == 0){
mep.erase(it->fi);
--it;
}
--it;
ans += it->fi;
}
last = ans;
cout << ans << '\n';
}
return 0;
}
Compilation message
diameter.cpp: In function 'void solve_sub2(int, int, int)':
diameter.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < lst[cur].size(); ++i){
| ~~^~~~~~~~~~~~~~~~~
diameter.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < lst[cur].size(); ++i){
| ~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'ii dfs(int, int, int)':
diameter.cpp:172:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0; i < lst[idx].size(); ++i){
| ~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:247:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for(int i = 0; i < vecs.size(); ++i){
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12384 KB |
Output is correct |
2 |
Correct |
9 ms |
12388 KB |
Output is correct |
3 |
Correct |
7 ms |
12420 KB |
Output is correct |
4 |
Correct |
7 ms |
12400 KB |
Output is correct |
5 |
Correct |
7 ms |
12440 KB |
Output is correct |
6 |
Correct |
6 ms |
12468 KB |
Output is correct |
7 |
Correct |
7 ms |
12372 KB |
Output is correct |
8 |
Correct |
7 ms |
12372 KB |
Output is correct |
9 |
Correct |
7 ms |
12404 KB |
Output is correct |
10 |
Correct |
6 ms |
12372 KB |
Output is correct |
11 |
Correct |
7 ms |
12372 KB |
Output is correct |
12 |
Correct |
6 ms |
12468 KB |
Output is correct |
13 |
Correct |
7 ms |
12468 KB |
Output is correct |
14 |
Correct |
8 ms |
12472 KB |
Output is correct |
15 |
Correct |
7 ms |
12372 KB |
Output is correct |
16 |
Correct |
7 ms |
12464 KB |
Output is correct |
17 |
Correct |
8 ms |
12372 KB |
Output is correct |
18 |
Correct |
7 ms |
12464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12384 KB |
Output is correct |
2 |
Correct |
9 ms |
12388 KB |
Output is correct |
3 |
Correct |
7 ms |
12420 KB |
Output is correct |
4 |
Correct |
7 ms |
12400 KB |
Output is correct |
5 |
Correct |
7 ms |
12440 KB |
Output is correct |
6 |
Correct |
6 ms |
12468 KB |
Output is correct |
7 |
Correct |
7 ms |
12372 KB |
Output is correct |
8 |
Correct |
7 ms |
12372 KB |
Output is correct |
9 |
Correct |
7 ms |
12404 KB |
Output is correct |
10 |
Correct |
6 ms |
12372 KB |
Output is correct |
11 |
Correct |
7 ms |
12372 KB |
Output is correct |
12 |
Correct |
6 ms |
12468 KB |
Output is correct |
13 |
Correct |
7 ms |
12468 KB |
Output is correct |
14 |
Correct |
8 ms |
12472 KB |
Output is correct |
15 |
Correct |
7 ms |
12372 KB |
Output is correct |
16 |
Correct |
7 ms |
12464 KB |
Output is correct |
17 |
Correct |
8 ms |
12372 KB |
Output is correct |
18 |
Correct |
7 ms |
12464 KB |
Output is correct |
19 |
Correct |
312 ms |
12636 KB |
Output is correct |
20 |
Correct |
292 ms |
12632 KB |
Output is correct |
21 |
Correct |
295 ms |
12756 KB |
Output is correct |
22 |
Correct |
318 ms |
12620 KB |
Output is correct |
23 |
Correct |
1992 ms |
13048 KB |
Output is correct |
24 |
Correct |
1927 ms |
13160 KB |
Output is correct |
25 |
Correct |
1957 ms |
13144 KB |
Output is correct |
26 |
Correct |
1842 ms |
13180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12372 KB |
Output is correct |
2 |
Correct |
7 ms |
12372 KB |
Output is correct |
3 |
Correct |
8 ms |
12500 KB |
Output is correct |
4 |
Correct |
14 ms |
12756 KB |
Output is correct |
5 |
Correct |
42 ms |
13196 KB |
Output is correct |
6 |
Correct |
8 ms |
12372 KB |
Output is correct |
7 |
Correct |
7 ms |
12500 KB |
Output is correct |
8 |
Correct |
10 ms |
12500 KB |
Output is correct |
9 |
Correct |
48 ms |
12552 KB |
Output is correct |
10 |
Correct |
16 ms |
12732 KB |
Output is correct |
11 |
Correct |
44 ms |
13388 KB |
Output is correct |
12 |
Correct |
9 ms |
12868 KB |
Output is correct |
13 |
Correct |
8 ms |
12864 KB |
Output is correct |
14 |
Correct |
9 ms |
12864 KB |
Output is correct |
15 |
Correct |
18 ms |
13172 KB |
Output is correct |
16 |
Correct |
55 ms |
13820 KB |
Output is correct |
17 |
Correct |
42 ms |
18084 KB |
Output is correct |
18 |
Correct |
42 ms |
18164 KB |
Output is correct |
19 |
Correct |
46 ms |
18216 KB |
Output is correct |
20 |
Correct |
57 ms |
18276 KB |
Output is correct |
21 |
Correct |
104 ms |
19312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
12588 KB |
Output is correct |
2 |
Execution timed out |
5044 ms |
12608 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
18 ms |
25036 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12384 KB |
Output is correct |
2 |
Correct |
9 ms |
12388 KB |
Output is correct |
3 |
Correct |
7 ms |
12420 KB |
Output is correct |
4 |
Correct |
7 ms |
12400 KB |
Output is correct |
5 |
Correct |
7 ms |
12440 KB |
Output is correct |
6 |
Correct |
6 ms |
12468 KB |
Output is correct |
7 |
Correct |
7 ms |
12372 KB |
Output is correct |
8 |
Correct |
7 ms |
12372 KB |
Output is correct |
9 |
Correct |
7 ms |
12404 KB |
Output is correct |
10 |
Correct |
6 ms |
12372 KB |
Output is correct |
11 |
Correct |
7 ms |
12372 KB |
Output is correct |
12 |
Correct |
6 ms |
12468 KB |
Output is correct |
13 |
Correct |
7 ms |
12468 KB |
Output is correct |
14 |
Correct |
8 ms |
12472 KB |
Output is correct |
15 |
Correct |
7 ms |
12372 KB |
Output is correct |
16 |
Correct |
7 ms |
12464 KB |
Output is correct |
17 |
Correct |
8 ms |
12372 KB |
Output is correct |
18 |
Correct |
7 ms |
12464 KB |
Output is correct |
19 |
Correct |
312 ms |
12636 KB |
Output is correct |
20 |
Correct |
292 ms |
12632 KB |
Output is correct |
21 |
Correct |
295 ms |
12756 KB |
Output is correct |
22 |
Correct |
318 ms |
12620 KB |
Output is correct |
23 |
Correct |
1992 ms |
13048 KB |
Output is correct |
24 |
Correct |
1927 ms |
13160 KB |
Output is correct |
25 |
Correct |
1957 ms |
13144 KB |
Output is correct |
26 |
Correct |
1842 ms |
13180 KB |
Output is correct |
27 |
Correct |
6 ms |
12372 KB |
Output is correct |
28 |
Correct |
7 ms |
12372 KB |
Output is correct |
29 |
Correct |
8 ms |
12500 KB |
Output is correct |
30 |
Correct |
14 ms |
12756 KB |
Output is correct |
31 |
Correct |
42 ms |
13196 KB |
Output is correct |
32 |
Correct |
8 ms |
12372 KB |
Output is correct |
33 |
Correct |
7 ms |
12500 KB |
Output is correct |
34 |
Correct |
10 ms |
12500 KB |
Output is correct |
35 |
Correct |
48 ms |
12552 KB |
Output is correct |
36 |
Correct |
16 ms |
12732 KB |
Output is correct |
37 |
Correct |
44 ms |
13388 KB |
Output is correct |
38 |
Correct |
9 ms |
12868 KB |
Output is correct |
39 |
Correct |
8 ms |
12864 KB |
Output is correct |
40 |
Correct |
9 ms |
12864 KB |
Output is correct |
41 |
Correct |
18 ms |
13172 KB |
Output is correct |
42 |
Correct |
55 ms |
13820 KB |
Output is correct |
43 |
Correct |
42 ms |
18084 KB |
Output is correct |
44 |
Correct |
42 ms |
18164 KB |
Output is correct |
45 |
Correct |
46 ms |
18216 KB |
Output is correct |
46 |
Correct |
57 ms |
18276 KB |
Output is correct |
47 |
Correct |
104 ms |
19312 KB |
Output is correct |
48 |
Correct |
58 ms |
12588 KB |
Output is correct |
49 |
Execution timed out |
5044 ms |
12608 KB |
Time limit exceeded |
50 |
Halted |
0 ms |
0 KB |
- |