Submission #944056

#	Time	Username	Problem	Language	Result	Execution time	Memory
944056		vjudge1	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	2463 ms	21252 KiB

diameter

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define rep(i,s,f) for(int i = s;i < f;i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back

const int N = 1e5 + 1;

set<pair<int,int>> g[N];
int mx,fnd;

void dfs(int n,int p,int dis,bool check){
	if(dis > mx){
		mx = dis;
		fnd = n;
	}
	for(auto [to,cost] : g[n]){
		if(to != p){
			dfs(to,n,dis + cost,check);
		}
	}
}

void solve(){
	
	int n,m,w;
	cin >> n >> m >> w;
	array<int,3> ind[n];
	for(int i = 0;i < n - 1;i++){
		int a,b,c;
		cin >> a >> b >> c;
		g[a].insert({b,c});
		g[b].insert({a,c});
		ind[i] = {a,b,c};
	}
	int last = 0;
	for(int i = 0;i < m;i++){
		int d,e;
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		auto &[a,b,c] = ind[d];
		g[a].erase({b,c});
		g[b].erase({a,c});
		g[a].insert({b,e});
		g[b].insert({a,e});
		ind[d][2] = e;
		if(n <= 5000 && m <= 5000){
			dfs(1,-1,0,0);
			dfs(fnd,-1,0,1);
			cout << mx << "\n";
			last = mx;
			mx = 0;
		}
	}
	
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}
	

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