제출 #1232888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232888		Adnanboi	Election (BOI18_election)	C++20	0 / 100	0 ms	320 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

void solve(){
	int n, q, wlim;
	cin>>n>>q>>wlim;
	vector<array<int, 3>> edges(n - 1);
	vector<vector<pair<int, int>>> adj(n + 1);
	for(int i = 0; i < n - 1; ++i){
		int u, v, w;
		cin>>u>>v>>w;
		edges[i] = {u, v, w};
		adj[u].push_back(make_pair(v, i));
		adj[v].push_back(make_pair(u, i));
	}

	vector<int> weight(n - 1);
	for(int i = 0; i < n - 1; ++i)
		weight[i] = edges[i][2];

	vector<int> depth(n + 1), parent(n + 1), from_edge(n + 1);
	function<void(int, int)> dfs = [&](int u, int p){
		for(int i = 0; i < adj[u].size(); ++i){
			int v = adj[u][i].first;
			int idx = adj[u][i].second;
			if(v == p) continue;
			depth[v] = depth[u] + weight[idx];
			parent[v] = u;
			from_edge[v] = idx;
			dfs(v, u);
		}
	};

	dfs(1, -1);

	vector<int> max1(n + 1), max2(n + 1);

	function<int(int)> dfs_depths = [&](int u){
		int d1 = 0, d2 = 0;
		for(int i = 0; i < adj[u].size(); ++i){
			int v = adj[u][i].first;
			int idx = adj[u][i].second;
			if(v == parent[u]) continue;
			int d = dfs_depths(v) + weight[idx];
			if(d > d1){
				d2 = d1;
				d1 = d;
			}else if(d > d2){
				d2 = d;
			}
		}
		max1[u] = d1;
		max2[u] = d2;
		return d1;
	};

	dfs_depths(1);

	int result = max1[1] + max2[1];

	while(q--){
		int x, y;
		cin>>x>>y;
		x = (x + result) % (n - 1);
		y = (y + result) % wlim;
		int u = edges[x][0], v = edges[x][1];
		if(parent[v] == u) swap(u, v);

		int diff = y - weight[x];
		weight[x] = y;

		int curr = v;
		while(true){
			int d1 = 0, d2 = 0;
			for(int i = 0; i < adj[curr].size(); ++i){
				int child = adj[curr][i].first;
				int idx = adj[curr][i].second;
				if(child == parent[curr]) continue;
				int d = max1[child] + weight[idx];
				if(d > d1){
					d2 = d1;
					d1 = d;
				}else if(d > d2){
					d2 = d;
				}
			}
			if(max1[curr] == d1 && max2[curr] == d2) break;
			max1[curr] = d1;
			max2[curr] = d2;
			if(curr == 1) break;
			curr = parent[curr];
		}

		result = max1[1] + max2[1];
		cout<<result<<'\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18