Submission #1128562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128562		daoquanglinh2007	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3457 ms	210144 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair <int, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 1e5;

struct edge{
	int u, v;
	ll l;
};

int n, q;
edge E[NM+5];
ll w;
vector <pil> adj[NM+5];
int parent_cen[NM+5], num[NM+5], fnum[NM+5], sz[NM+5], timer;
bool del[NM+5];
vector <int> tmp, vlist[NM+5], tin[NM+5], tout[NM+5], tour[NM+5], f[NM+5];
vector <ll> d[NM+5], st[NM+5], lazy[NM+5];
multiset <ll, greater <ll> > mxf[NM+5], S;

void dfs_sz(int u, int p){
	tmp.push_back(u);
	sz[u] = 1;
	for (pil _ : adj[u]){
		int v = _.fi;
		if (v == p || del[v]) continue;
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
}

int dfs_fc(int rt, int u, int p){
	for (pil _ : adj[u]){
		int v = _.fi;
		if (v == p || del[v]) continue;
		if (sz[v] > sz[rt]/2) return dfs_fc(rt, v, u);
	}
	return u;
}

void dfs_dp(int rt, int u, int p, int pos_u){
	if (u == rt){
		f[rt][pos_u] = -1;
		d[rt][pos_u] = 0;
	}
	tin[rt][pos_u] = timer++;
	tour[rt][timer-1] = pos_u;
	for (pil _ : adj[u]){
		int v = _.fi;
		ll l = _.se;
		if (v == p || del[v]) continue;
		int pos_v = lower_bound(vlist[rt].begin(), vlist[rt].end(), v)-vlist[rt].begin();
		if (u == rt) f[rt][pos_v] = pos_v;
		else f[rt][pos_v] = f[rt][pos_u];
		d[rt][pos_v] = d[rt][pos_u]+l;
		dfs_dp(rt, v, u, pos_v);
	}
	tout[rt][pos_u] = timer-1;
}

void build(int rt, int id, int l, int r){
	if (l == r){
		st[rt][id] = d[rt][tour[rt][l]];
		return;
	}
	int mid = (l+r)/2;
	build(rt, 2*id, l, mid);
	build(rt, 2*id+1, mid+1, r);
	st[rt][id] = max(st[rt][2*id], st[rt][2*id+1]);
}

void down(int rt, int id){
	st[rt][2*id] += lazy[rt][id], st[rt][2*id+1] += lazy[rt][id];
	lazy[rt][2*id] += lazy[rt][id], lazy[rt][2*id+1] += lazy[rt][id];
	lazy[rt][id] = 0;
}

void update(int rt, int id, int l, int r, int u, int v, ll val){
	if (u > v || v < l || u > r) return;
	if (l >= u && r <= v){
		st[rt][id] += val;
		lazy[rt][id] += val;
		return;
	}
	down(rt, id);
	int mid = (l+r)/2;
	update(rt, 2*id, l, mid, u, v, val);
	update(rt, 2*id+1, mid+1, r, u, v, val);
	st[rt][id] = max(st[rt][2*id], st[rt][2*id+1]);
}

ll get(int rt, int id, int l, int r, int u, int v){
	if (u > v || v < l || u > r) return -1;
	if (l >= u && r <= v) return st[rt][id];
	down(rt, id);
	int mid = (l+r)/2;
	return max(get(rt, 2*id, l, mid, u, v), get(rt, 2*id+1, mid+1, r, u, v));
}

ll get_diameter(int rt){
	if (mxf[rt].empty()) return 0;
	if (isz(mxf[rt]) == 1) return *mxf[rt].begin();
	return *mxf[rt].begin() + *(next(mxf[rt].begin()));
}

void decompose(int u, int p){
	tmp.clear();
	dfs_sz(u, -1);
	u = dfs_fc(u, u, -1);
	parent_cen[u] = p;
	del[u] = 1;
	num[u] = isz(tmp);
	sort(tmp.begin(), tmp.end());
	vlist[u] = tmp;
	tin[u].resize(num[u]); tout[u].resize(num[u]); tour[u].resize(num[u]);
	f[u].resize(num[u]);
	d[u].resize(num[u]);
	
	timer = 0;
	dfs_dp(u, u, -1, lower_bound(vlist[u].begin(), vlist[u].end(), u)-vlist[u].begin());
	st[u].resize(4*num[u]+1);
	lazy[u].assign(4*num[u]+1, 0LL);
	build(u, 1, 0, num[u]-1);
	
	mxf[u].clear();
	for (int i = 0; i < num[u]; i++){
		if (f[u][i] != i) continue;
		mxf[u].insert(get(u, 1, 0, num[u]-1, tin[u][i], tout[u][i]));
	}
	S.insert(get_diameter(u));
	
	for (pil _ : adj[u]){
		int v = _.fi;
		if (del[v]) continue;
		decompose(v, u);
	}
}

void add(int rt, int u, int v, ll val){
	S.erase(S.find(get_diameter(rt)));
	int pos_u = lower_bound(vlist[rt].begin(), vlist[rt].end(), u)-vlist[rt].begin();
	int pos_v = lower_bound(vlist[rt].begin(), vlist[rt].end(), v)-vlist[rt].begin();
	if (tin[rt][pos_u] < tin[rt][pos_v]){
		ll pre = get(rt, 1, 0, num[rt]-1, tin[rt][f[rt][pos_v]], tout[rt][f[rt][pos_v]]);
		update(rt, 1, 0, num[rt]-1, tin[rt][pos_v], tout[rt][pos_v], val);
		ll cur = get(rt, 1, 0, num[rt]-1, tin[rt][f[rt][pos_v]], tout[rt][f[rt][pos_v]]);
		if (pre != cur){
			mxf[rt].erase(mxf[rt].find(pre));
			mxf[rt].insert(cur);
		}
	}
	else{
		ll pre = get(rt, 1, 0, num[rt]-1, tin[rt][f[rt][pos_u]], tout[rt][f[rt][pos_u]]);
		update(rt, 1, 0, num[rt]-1, tin[rt][pos_u], tout[rt][pos_u], val);
		ll cur = get(rt, 1, 0, num[rt]-1, tin[rt][f[rt][pos_u]], tout[rt][f[rt][pos_u]]);
		if (pre != cur){
			mxf[rt].erase(mxf[rt].find(pre));
			mxf[rt].insert(cur);
		}
	}
	S.insert(get_diameter(rt));
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q >> w;
	for (int i = 0; i < n-1; i++){
		cin >> E[i].u >> E[i].v >> E[i].l;
		adj[E[i].u].push_back(mp(E[i].v, E[i].l));
		adj[E[i].v].push_back(mp(E[i].u, E[i].l));
	}
	decompose(1, -1);
	
	ll lst = 0;
	while (q--){
		int d; ll e;
		cin >> d >> e;
		d = (d+lst)%(n-1);
		e = (e+lst)%w;
		
		if (num[E[d].u] < num[E[d].v]) swap(E[d].u, E[d].v);
		for (int rt = E[d].u; rt != -1; rt = parent_cen[rt])
			add(rt, E[d].u, E[d].v, e-E[d].l);
		E[d].l = e;
		
		lst = *S.begin();
		cout << lst << '\n';
	}
	
	return 0;
}

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