Submission #716433

#	Time	Username	Problem	Language	Result	Execution time	Memory
716433		ajab_01	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	1770 ms	12436 KiB

diameter

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

#define int long long

const int N = 1e5 + 5;
vector<pair<pair<int , int> , int> > edge;
vector<pair<int , int> > g[N];
int level[N] , d , e , n , q , w , last;

void dfs(int ver , int par){
	for(auto i : g[ver]){
		int uu = i.first , ww = i.second;
		if(uu == par) continue;
		level[uu] = level[ver] + ww;
		dfs(uu , ver);
	}
}

void cal(){
	for(int i = 1 ; i <= n ; i++) g[i].clear();
	for(auto i : edge){
		int U = i.first.first , V = i.first.second , W = i.second;
		g[U].push_back({V , W});
		g[V].push_back({U , W});
	}

	dfs(1 , 0);

	int mx = 0 , vr = 1;

	for(int i = 1 ; i <= n ; i++){
		if(mx < level[i]){
			mx = level[i];
			vr = i;
		}
	}

	level[vr] = 0;

	dfs(vr , 0);

	mx = 0;
	for(int i = 1 ; i <= n ; i++)
		mx = max(mx , level[i]);

	cout << mx << '\n';
	last = mx;
	return;
}

void solve1(){
	while(q--){
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		pair<pair<int , int> , int> p;
		p = edge[d];
		p.second = e;
		swap(edge[d] , p);
		cal();
	}
}

int32_t main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q >> w;
	for(int i = 0 ; i < n - 1 ; i++){
		int U , V , W;
		cin >> U >> V >> W;
		g[U].push_back({V , W});
		g[V].push_back({U , W});
		edge.push_back({{U , V} , W});
	}
	if(n <= 5000 && q <= 5000){
		solve1();
		return 0;
	}
	return 0;
}

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