Submission #716484

#	Time	Username	Problem	Language	Result	Execution time	Memory
716484		ajab_01	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	1710 ms	46972 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] , val[N] , level[N] , d , e , n , q , w , last , star = -1;
bool ch = 1;
multiset<int , greater<int>> st;
priority_queue<pair<int , int>> pq;

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 solve3(){
	for(int i = n / 2 ; i >= 1 ; i--){
		dp[i] = max(dp[i << 1] + val[i << 1] , dp[i << 1 | 1] + val[i << 1 | 1]);
		pq.push({dp[i << 1] + dp[i << 1 | 1] + val[i << 1] + val[i << 1 | 1] , i});
	}
	while(q--){
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		int ver = edge[d].first.second;
		val[ver] = e;
		while(ver != 1){
			ver >>= 1;
			dp[ver] = max(dp[ver << 1] + val[ver << 1] , dp[ver <<  1 | 1] + val[ver << 1 | 1]);
			pq.push({dp[ver << 1] + dp[ver << 1 | 1] + val[ver << 1] + val[ver << 1 | 1] , ver});
		}
		while(!pq.empty()){
			pair<int , int> p = pq.top();
			int vl = p.first , vr = p.second;
			if(dp[vr << 1] + dp[vr << 1 | 1] + val[vr << 1] + val[vr << 1 | 1] == vl) break;
			pq.pop();
		}
		last = pq.top().first;
		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});
		if(U > V) swap(U , V);
		edge.push_back({{U , V} , W});
		if(g[U].size() == n - 1) star = U;
		if(g[V].size() == n - 1) star = V;
		if(abs(V - 2 * U) > 1) ch = 0;
		val[V] = W;
	}
	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 'int32_t main()':
diameter.cpp:123: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]
  123 |   if(g[U].size() == n - 1) star = U;
      |      ~~~~~~~~~~~~^~~~~~~~
diameter.cpp:124: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]
  124 |   if(g[V].size() == n - 1) star = V;
      |      ~~~~~~~~~~~~^~~~~~~~

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