Submission #716438

#	Time	Username	Problem	Language	Result	Execution time	Memory
716438		ajab_01	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	1758 ms	17284 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 , star = -1;

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

void solve2(){
	multiset<int , greater<int>> st;
	for(auto i : edge)
		st.insert(i.second);
	while(q--){
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		st.erase(st.find(edge[d].second));
		pair<pair<int , int> , int> p;
		p = edge[d];
		p.second = e;
		swap(edge[d] , p);
		st.insert(e);
		last = *st.begin() + *next(st.begin());
		cout << last << '\n';
	}
}

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(g[U].size() == n - 1) star = U;
		if(g[V].size() == n - 1) star = V;
	}
	if(n <= 5000 && q <= 5000){
		solve1();
		return 0;
	}
	if(star != -1){
		solve2();
		return 0;
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int32_t main()':
diameter.cpp:93:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   93 |   if(g[U].size() == n - 1) star = U;
      |      ~~~~~~~~~~~~^~~~~~~~
diameter.cpp:94:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   94 |   if(g[V].size() == n - 1) star = V;
      |      ~~~~~~~~~~~~^~~~~~~~

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