제출 #854243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854243		daoquanglinh2007	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5036 ms	438208 KiB

diameter

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

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

#define ll long long
#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;

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

void dfs_sz(int u, int par){
	sz[u] = 1;
	int v;
	for (int i = 0; i < isz(adj[u]); i++){
		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){
	int v;
	for (int i = 0; i < isz(adj[u]); i++){
		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);
	int v; ll c;
	for (int i = 0; i < isz(adj[u]); i++){
		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] = 0LL;
	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] = 0LL;
}

void update(int rt, int id, int l, int r, int u, int v, ll 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]);
}

ll 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));
}

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

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

void modify(int rt, int u, int v, ll 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);
		int l = tin[rt][f[rt][v]], r = tout[rt][f[rt][v]];
		diam.erase(diam.find(get_diam(rt)));
		S[rt].erase(S[rt].find(get(rt, 1, 1, sub[rt], l, r)));
		update(rt, 1, 1, sub[rt], tin[rt][v], tout[rt][v], x);
		S[rt].insert(get(rt, 1, 1, sub[rt], l, r));
		diam.insert(get_diam(rt));
	}
	modify(parent_cen[rt], u, v, x);
}

int 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;
		ll e;
		cin >> d >> e;
		d = ((ll)d+last)%(n-1)+1;
		e = (e+last) % w;
		modified.clear();
		modify(a[d], a[d], b[d], e-c[d]);
		modify(b[d], a[d], b[d], e-c[d]);
		c[d] = 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