Submission #618949

#	Time	Username	Problem	Language	Result	Execution time	Memory
618949		sentheta	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5069 ms	11784 KiB

diameter

#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define V vector
#define Int long long
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define all(x) (x).begin(), (x).end()

#define int long long
#define pii pair<int,int>

const int N = 1e5+5;
int n, q, wlim;
V<array<int,3>> edges;
V<pair<int,int>> queries;

struct Sub1{
	V<int> adj[N];
	int mxdist = 0, mxnode = -1;
	void dfs(int x,int par=-1,int dist=0){
		if(dist >= mxdist){
			mxdist = dist;
			mxnode = x;
		}

		for(int id : adj[x]){
			int y = edges[id][0]^edges[id][1]^x;
			int w = edges[id][2];
			if(y==par) continue;

			dfs(y,x, dist+w);
		}
	}
	void run(){
		rep(i,0,n-1){
			auto[u,v,w] = edges[i];
			adj[u].push_back(i);
			adj[v].push_back(i);
		}

		int last = 0;
		for(auto[i,w] : queries){
			i = (i+last)%(n-1);
			w = (w+last)%wlim;
			edges[i][2] = w;

			mxdist = 0;
			dfs(1);
			dfs(mxnode);

			cout << mxdist << nl;
			last = mxdist;
		}
	}
};

struct Sub3{
	int arr[N];
	multiset<int> s;
	void run(){
		rep(i,0,n-1){
			auto[u,v,w] = edges[i];
			if(u==1) swap(u,v);

			arr[u] = w;
			s.insert(w);
		}

		int last = 0;
		for(auto[i,w] : queries){
			i = (i+last)%(n-1);
			w = (w+last)%wlim;
			auto[u,v,ww] = edges[i];
			if(u==1) swap(u,v);

			s.erase(s.find(arr[u]));
			arr[u] = w;
			s.insert(arr[u]);

			int ans = *prev(s.end());
			if(n > 2){
				ans += *prev(prev(s.end()));
			}

			cout << ans << nl;
			last = ans;
		}
	}
};

struct Sub4{
	int p[N];
	int ans[N], path[N];
	void dp_trans(int x){
		// 2 children
		if(2*x+1 <= n){
			ans[x] = max({
				ans[2*x], ans[2*x+1],
				path[2*x] + edges[p[2*x]][2]
				+ path[2*x+1] + edges[p[2*x+1]][2] 
			});
			path[x] = max({
				path[2*x] + edges[p[2*x]][2],
				path[2*x+1] + edges[p[2*x+1]][2] 
			});
		}
		// 1 children
		else if(2*x <= n){
			ans[x] = path[2*x] + edges[p[2*x]][2];
			path[x] = path[2*x] + edges[p[2*x]][2];
		}
		// 0 children
		else{
			ans[x] = path[x] = 0;
		}

		if(x!=1) dp_trans(p[x]);
	}
	void run(){
		rep(i,0,n-1){
			auto[u,v,w] = edges[i];
			p[v] = i;
		}
		// rep(i,1,n+1){
		for(int i=n; i>=1; i--){
			dp_trans(i);
		}
		// rep(i,1,n+1){
		// 	dbg(i);
		// 	dbg(ans[i]); dbg(path[i]);
		// }

		int last = 0;
		for(auto[i,w] : queries){
			i = (i+last)%(n-1);
			w = (w+last)%wlim;

			edges[i][2] = w;
			dp_trans(edges[i][0]);

			cout << ans[1] << nl;
			last = ans[1];
		}
	}
};

signed main(){

	cin >> n >> q >> wlim;
	
	rep(i,0,n-1){
		int u, v, w;
		cin >> u >> v >> w;

		edges.push_back({u,v,w});
	}
	rep(i,0,q){
		int idx, w;
		cin >> idx >> w;

		queries.push_back({idx,w});
	}


	bool sub3 = 1, sub4 = 1;
	rep(i,0,n-1){
		auto[u,v,w] = edges[i];
		if(u > v) swap(u,v);

		sub3 &= u==1;
		sub4 &= v/2==u;
	}
	if(sub3){
		Sub3 sub; sub.run(); return 0;
	}
	if(sub4){
		// dbg(sub4);
		Sub4 sub; sub.run(); return 0;
	}

	Sub1 sub; sub.run(); return 0;
}

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