Submission #716468

#	Time	Username	Problem	Language	Result	Execution time	Memory
716468		faribourz	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	900 ms	23992 KiB

diameter

// Only GOD
// Believe in yourself!
// -o Sango zadam be shishe 
// -o Comeback bezan hamishe!
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
#define pb push_back
#define F first
#define S second
#define bit(x, y) (x >> y)&1
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define mid ((l+r)>>1)
#define lid (id << 1)
#define rid (lid | 1)
const int N = 3e5+10;
const int INF = 1e9+10;
 
int n, q, W;
vector<pii> G[N];
int edge[N], dp[N], maxout[N], lst, h[N];
pii EDGE[N];
map<pii, int> E;
// chinese seg:)
void upd(int id){
	int mx1 = maxout[lid] + E[{id, lid}], mx2 = maxout[rid] + E[{id, rid}];
	maxout[id] = max(mx1, mx2);
	dp[id] = max({mx1 + mx2, dp[lid], dp[rid]});
	lst = max({lst, dp[id], dp[rid], dp[lid], maxout[lid], maxout[id], maxout[rid]});
	id >>= 1;
	for(; id > 0; id >>= 1){
		mx1 = maxout[lid] + E[{id, lid}], mx2 = maxout[rid] + E[{id, rid}];
		maxout[id] = max(mx1, mx2);
		dp[id] = max({mx1 + mx2, dp[lid], dp[rid]});
		lst = max({lst, dp[id], dp[rid], dp[lid], maxout[lid], maxout[id], maxout[rid]});
	}
}
void DFS(int v, int p = -1){
	int mx1 = -1, mx2 = -1;
	for(auto x : G[v]){
		if(x.F == p)
			continue;
		h[x.F] = h[v] + 1;
		DFS(x.F, v);
		if(edge[x.S] + maxout[x.F] >= mx1){
			swap(mx1, mx2);
			mx1 = edge[x.S] + maxout[x.F]; 
		}
		else if(edge[x.S] + maxout[x.F] > mx2){
			mx2 = edge[x.S] + maxout[x.F]; 
		}
	}
	maxout[v] = (mx1==-1 ? 0 : mx1);
	if(mx2 != -1){
		dp[v] = mx1 + mx2;
	}
}
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 v, u, w;
		cin >> v >> u >> w;
		G[v].pb({u, i});
		G[u].pb({v, i});
		edge[i] = w;
		if(u < v)
			swap(v, u);
		EDGE[i]={v, u};
		E[{v, u}]=w;
	}	
	lst = 0;
	if(n <= 5001 && q <= 5001){
		while(q--){
			int d, e;
			cin >> d >> e;
			edge[(d+lst)%(n-1)] = (e+lst)%W;
			DFS(1);
			lst = 0;
			for(int i = 1; i <= n; i++)
				lst = max({lst, dp[i], maxout[i]});
			cout << lst << '\n';
		}
	}
	else if(sz(G[1]) == n-1){
		set<pii , greater<pii>> s;
		for(int i = 0; i < n-1; i++){
			s.insert({edge[i], i});
		}
		while(q--){
			int d, e;
			cin >> d >> e;
			s.erase({edge[(d+lst)%(n-1)], (d+lst)%(n-1)});
			edge[(d+lst)%(n-1)] = (e+lst)%W;
			s.insert({edge[(d+lst)%(n-1)], (d+lst)%(n-1)});
			if(sz(s)==1){
				lst = (*s.begin()).F;
			}
			else{
				auto itr = s.begin();
				lst = (*itr).F;
				itr++;
				lst += (*itr).F;
			}
			cout << lst << '\n';
		}
	}
	else{
		DFS(1);
		while(q--){
			int d, e;
			cin >> d >> e;
			edge[(d+lst)%(n-1)] = (e+lst)%W;
			int v = EDGE[(d+lst)%(n-1)].F, u = EDGE[(d+lst)%(n-1)].S;
			if(u < v)
				swap(v, u);
			E[{v, u}] = (e+lst)%W;
			lst = 0;
			upd(v);
			cout << lst << '\n';
		}
	}
}

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