Submission #1109557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109557		ngmtuan	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	5062 ms	35328 KiB

diameter

// https://oj.uz/problem/view/CEOI19_diameter
// https://dmoj.ca/problem/ceoi19p2/editorial
#include<bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
using namespace std;

const int N=100005;
int n,q;
ll W;
vector<pair<int,ll>> g[N];
int fa[N];
int L[N], R[N], timer;
ll d[N];
int st[N<<1];
vector<array<ll,3>> edges;
void dfs(int u) {
	for (auto &[v, w] : g[u]) {
		if (v == fa[u]) {
			continue;
		}
		d[v] = d[u] + w;
		fa[v] = u;
		dfs(v);
	}
}
void tour(int u) {
	st[++timer] = u;
	L[u] = timer;
	for (auto &[v, w] : g[u]) {
		if (v == fa[u]) continue;
		tour(v);
		st[++timer] = u;
	}
	R[u] = timer;
}
/*
    a,b,c
    0 -> a
    1 -> ab
    2 -> bc
    3 -> abc
*/
#define lay(); int mid = (l + r) >> 1; int ls = x + 1, rs = x + ((mid - l + 1) << 1);
struct node {
    ll mn, lazy;
    ll ans[4];
} tree[N<<2];
node unite(node a,node b){
    node ans;
    ans.lazy = 0;
    ans.mn = min(a.mn,b.mn);
    ans.ans[0] = max(a.ans[0],b.ans[0]);
    ans.ans[1] = max(a.ans[1],b.ans[1]);
    ans.ans[1] = max(ans.ans[1],a.ans[0] - 2*b.mn);
    ans.ans[2] = max({a.ans[2],b.ans[2],b.ans[0] - 2*a.mn});
    ans.ans[3] = max({a.ans[3],b.ans[3],a.ans[0] + b.ans[2],a.ans[1] + b.ans[0]});
    return ans;
}
void build(int x,int l,int r){
    if(l==r){
        tree[x].mn = d[st[l]];
        tree[x].ans[0] = d[st[l]];
        tree[x].ans[1] = tree[x].ans[2] = -d[st[l]];
        tree[x].ans[3] = 0;
        return ;
    }
    lay();
    build(ls,l,mid);
    build(rs,mid+1,r);
    tree[x] = unite(tree[ls],tree[rs]);
}
void apply(int x,ll v){
    tree[x].mn += v;
    tree[x].ans[0] += v;
    tree[x].ans[1] -= v;
    tree[x].ans[2] -= v;
    tree[x].lazy += v;
}
void push(int x,int l,int r){
	if(tree[x].lazy==0)
		return;
	lay();
    apply(ls,tree[x].lazy);
    apply(rs,tree[x].lazy);
    tree[x].lazy = 0;
}
void update(int x,int l,int r,int ql,int qr,ll v){
	if(r<ql||qr<l) return;
    if(ql<=l and r<=qr){
        apply(x,v);
        return;
    }
    push(x,l,r);
    lay();
    update(ls,l,mid,ql,qr,v);
    update(rs,mid+1,r,ql,qr,v);
    tree[x] = unite(tree[ls],tree[rs]);
}
//node get(int x,int l,int r,int ql,int qr){
//    if(ql<=l&&r<=qr)
//		return tree[x];
//    lay();
//    push(x,l,r);
//    if(qr <= mid)
//		return get(ls,l,mid,ql,qr);
//    if(ql > mid)
//		return get(rs,mid+1,r,ql,qr);
//    return unite(get(ls,l,mid,ql,qr),get(rs,mid+1,r,ql,qr));
//}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q >> W;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
		edges.push_back({w, u, v});
	}
	dfs(1);
	tour(1);
	build(0,1,timer);
	ll last=0;
	while(q--){
		int d;
		ll w;
		cin>>d>>w;
		d=(d+last)%(n-1);
		w=(w+last)%W;
		int u=edges[d][1];
		int v=edges[d][2];
		if(fa[u]!=v)
			swap(u,v);
		update(0,1,timer,L[u],R[u],-edges[d][0]+w);
		edges[d][0]=w;
		last=tree[0].ans[3];
		cout<<last<<'\n';
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void dfs(int)':
diameter.cpp:19:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for (auto &[v, w] : g[u]) {
      |             ^
diameter.cpp: In function 'void tour(int)':
diameter.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |  for (auto &[v, w] : g[u]) {
      |             ^

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27