Submission #716461

#	Time	Username	Problem	Language	Result	Execution time	Memory
716461		ajab_01	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5052 ms	15008 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 dp[N][2] , level[N] , d , e , n , q , w , last , star = -1;
bool ch = 1;
multiset<int , greater<int>> st;

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

void pre(int ver , int pr){
	st.erase(st.find(dp[ver][0]));
	int mxx = 0;
	for(int i = 0 ; i < (int)g[ver].size() ; i++){
		int uu = g[ver][i].first , ww = g[ver][i].second;
		if(uu == pr) continue;
		dp[ver][0] = max(dp[ver][0] , dp[uu][1] + ww + mxx);
		mxx = max(mxx , dp[uu][1] + ww);
		dp[ver][1] = max(dp[ver][1] , dp[uu][1] + ww);
	}
	st.insert(dp[ver][0]);
}

void dfs2(int ver , int par){
	if(g[ver].size() == 1) return;
	for(auto i : g[ver]){
		int uu = i.first , ww = i.second;
		if(uu == par) continue;
		dfs2(uu , ver);
	}
	pre(ver , par);
}

void solve3(){
	dfs2(1 , 0);
	while(q--){
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		int uu = edge[d].first.first , vv = edge[d].first.second;
		pair<pair<int , int> , int> p;
		p = edge[d];
		p.second = e;
		swap(edge[d] , p);
		if(uu > vv) swap(uu , vv);
		pre(uu , uu / 2);
		while(uu != 1){
			uu /= 2;
			pre(uu , uu / 2);
		}
		last = *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(U > V) swap(U , V);
		if(abs(V - 2 * U) > 1) ch = 0;
	}
	if(n <= 5000 && q <= 5000){
		solve1();
		return 0;
	}
	if(star != -1){
		solve2();
		return 0;
	}
	if(ch){
		solve3();
		return 0;
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void dfs2(long long int, long long int)':
diameter.cpp:101:22: warning: unused variable 'ww' [-Wunused-variable]
  101 |   int uu = i.first , ww = i.second;
      |                      ^~
diameter.cpp: In function 'int32_t main()':
diameter.cpp:139: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]
  139 |   if(g[U].size() == n - 1) star = U;
      |      ~~~~~~~~~~~~^~~~~~~~
diameter.cpp:140: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]
  140 |   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