Submission #579276

#	Time	Username	Problem	Language	Result	Execution time	Memory
579276		amunduzbaev	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3818 ms	213508 KiB

diameter

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 1e5 + 5;
const int C = 18;
vector<ar<int, 2>> edges[N];

struct ST{
	vector<int> tree, add;
	int N;
	void init(int n){
		N = n;
		tree.resize(n << 2);
		add.resize(n << 2);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		add[x << 1] += add[x];
		add[x << 1 | 1] += add[x];
		tree[x << 1] += add[x];
		tree[x << 1 | 1] += add[x];
		add[x] = 0;
	}
	
	void aad(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += v;
			add[x] += v;
			return;
		} 
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		aad(l, r, v, lx, m, x << 1);
		aad(l, r, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void aad(int l, int r, int v){
		return aad(l, r, v, 0, N, 1);
	}
	
	int get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int get(int l, int r){
		return get(l, r, 0, N, 1);
	}
};

ST tree[N];
multiset<int> mx[N];
int par[N][C], sub[N], used[N];
int par2[N][C], ed[N][C], lvl;
int tin[N][C], tout[N][C], t;
vector<int> tt;

void dfs(int u, int p = -1){
	if(p == -1){
		tt.clear();
		t = -1;
		par[u][lvl] = u;
		par2[u][lvl] = -1;
		ed[u][lvl] = 0;
	} 
	tin[u][lvl] = ++t;
	sub[u] = 1;
	tt.push_back(u);
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		par[x[0]][lvl] = par[u][lvl];
		if(~par2[u][lvl]) par2[x[0]][lvl] = par2[u][lvl];
		else par2[x[0]][lvl] = x[0];
		ed[x[0]][lvl] = x[1];
		dfs(x[0], u);
		sub[u] += sub[x[0]];
	}
	
	tout[u][lvl] = t;
}

int cen(int u, int n, int p = -1){
	for(auto x : edges[u]){
		if(x[0] == p || used[x[0]]) continue;
		if(sub[x[0]] * 2 > n) return cen(x[0], n, u);
	} return u;
}

int res[N];

void dec(int u, int b = 0){ lvl = b;
	dfs(u);
	u = cen(u, sub[u]);
	dfs(u);
	//~ cout<<lvl<<" "<<u<<"\n";
	tree[u].init(sub[u]);
	for(auto x : tt){
		tree[u].aad(tin[x][lvl], tout[x][lvl], ed[x][lvl]);
		//~ cout<<x<<" "<<lvl<<" "<<ed[x][lvl]<<endl;
	}
	
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		mx[u].insert(tree[u].get(tin[x[0]][lvl], tout[x[0]][lvl]));
	}
	
	if((int)mx[u].size() > 1){
		auto it = --mx[u].end();
		res[u] = *it + *--it;
	} else if((int)mx[u].size()){
		res[u] = *--mx[u].end();
	}
	
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x[0]]) continue;
		dec(x[0], b + 1);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	multiset<int> ss;
	int n, q, w; cin>>n>>q>>w;
	vector<ar<int, 2>> E(n);
	for(int i=1;i<n;i++){
		int a, b, c; cin>>a>>b>>c;
		edges[a].push_back({b, c});
		edges[b].push_back({a, c});
		E[i] = {a, b};
	}
	
	memset(par, -1, sizeof par);
	dec(1);
	for(int i=1;i<=n;i++){
		ss.insert(res[i]);
	}
	
	auto upd = [&](int a, int b, int e){
		for(int i=0;i<C;i++){
			if(par[a][i] == -1 || par[b][i] == -1) continue;
			if(tin[a][i] > tin[b][i]) swap(a, b);
			int c = par[b][i];
			int x = par2[b][i];
			int old = tree[c].get(tin[x][i], tout[x][i]);
			tree[c].aad(tin[b][i], tout[b][i], -ed[b][i] + e);
			ed[b][i] = e;
			mx[c].erase(mx[c].find(old));
			mx[c].insert(tree[c].get(tin[x][i], tout[x][i]));
			ss.erase(ss.find(res[c]));
			if((int)mx[c].size() > 1){
				auto it = --mx[c].end();
				res[c] = *it + *--it;
			} else if((int)mx[c].size()){
				res[c] = *--mx[c].end();
			}
			
			ss.insert(res[c]);
		}
	};
	
	//~ for(auto x : ss) cout<<x<<" ";
	//~ cout<<endl;
	int last = 0;
	while(q--){
		int v, e; cin>>v>>e;
		v = (v + last) % (n - 1);
		e = (e + last) % w;
		upd(E[v + 1][0], E[v + 1][1], e);
		//~ for(auto x : ss) cout<<x<<" ";
		//~ cout<<endl;
		last = *--ss.end();
		cout<<last<<"\n";
	}
}
 

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