Submission #1128565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128565		daoquanglinh2007	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5112 ms	525788 KiB

diameter

#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")

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

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5;

int n, q, w, last = 0;
int a[NM+5], b[NM+5], c[NM+5];
vector <pii> adj[NM+5];
int sz[NM+5], parent_cen[NM+5];
bool del[NM+5];
int timer;
map <int, int> tin[NM+5], tout[NM+5], d[NM+5], f[NM+5];
vector <int> tour[NM+5], st[NM+5], lazy[NM+5];
multiset <int, greater <int> > S[NM+5];
multiset <int, greater <int> > diam;
map <int, bool> modified;

void dfs_sz(int u, int par){
	sz[u] = 1;
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (v == par || del[v]) continue;
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
}

int dfs_fc(int rt, int u, int par){
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (v == par || del[v]) continue;
		if (sz[v] > sz[rt]/2) return dfs_fc(rt, v, u);
	}
	return u;
}

void dfs(int rt, int u, int par){
	tin[rt][u] = ++timer;
	tour[rt].push_back(u);
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi, c = adj[u][i].se;
		if (v == par || del[v]) continue;
		d[rt][v] = d[rt][u]+c;
		dfs(rt, v, u);
	}
	tout[rt][u] = timer;
}

void build(int rt, int id, int l, int r){
	lazy[rt][id] = 0;
	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, int val){
	if (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]);
}

int get(int rt, int id, int l, int r, int u, int v){
	if (v < l || u > r) return 0LL;
	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));
}

int get_diam(int rt){
	if (S[rt].empty()) return 0;
	if (S[rt].size() == 1) return *S[rt].begin();
	return *S[rt].begin() + *(++S[rt].begin());
}

void centroid_dec(int u, int par){
	dfs_sz(u, -1);
	u = dfs_fc(u, u, -1);
	parent_cen[u] = par;
	del[u] = 1;
	
	d[u][u] = 0;
	timer = 0;
	tour[u].push_back(0);
	dfs(u, u, -1);
	int cur = tour[u][2];
	for (int i = 2; i < tour[u].size(); i++){
		if (i > tout[u][cur]) cur = tour[u][i];
		f[u][tour[u][i]] = cur;
	}
	
	st[u].resize(4*(tour[u].size()-1));
	lazy[u].resize(4*(tour[u].size()-1));
	build(u, 1, 1, tour[u].size()-1);
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (del[v]) continue;
		S[u].insert(get(u, 1, 1, tour[u].size()-1, tin[u][v], tout[u][v]));
	}
	diam.insert(get_diam(u));
	
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (del[v]) continue;
		centroid_dec(v, u);
	}
}

void modify(int rt, int u, int v, int x){
	if (rt == -1 || modified[rt]) return;
	if (tin[rt].count(u) && tin[rt].count(v)){
		modified[rt] = 1;
		if (tin[rt][u] > tin[rt][v]) swap(u, v);
		diam.erase(diam.find(get_diam(rt)));
		S[rt].erase(S[rt].find(get(rt, 1, 1, tour[rt].size()-1, tin[rt][f[rt][v]], tout[rt][f[rt][v]])));
		update(rt, 1, 1, tour[rt].size()-1, tin[rt][v], tout[rt][v], x);
		S[rt].insert(get(rt, 1, 1, tour[rt].size()-1, tin[rt][f[rt][v]], tout[rt][f[rt][v]]));
		diam.insert(get_diam(rt));
	}
	modify(parent_cen[rt], u, v, x);
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q >> w;
	for (int i = 1; i < n; i++){
		cin >> a[i] >> b[i] >> c[i];
		adj[a[i]].push_back(mp(b[i], c[i]));
		adj[b[i]].push_back(mp(a[i], c[i]));
	}
	centroid_dec(1, -1);
	while (q--){
		int d, e;
		cin >> d >> e;
		d = (d+last) % (n-1);
		e = (e+last) % w;
		modified.clear();
		modify(a[d+1], a[d+1], b[d+1], e-c[d+1]);
		modify(b[d+1], a[d+1], b[d+1], e-c[d+1]);
		c[d+1] = e;
		last = *diam.begin();
		cout << last << '\n';
	}
	return 0;
}

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