Submission #776439

#	Time	Username	Problem	Language	Result	Execution time	Memory
776439		Hacv16	Election Campaign (JOI15_election_campaign)	C++17	20 / 100	1097 ms	122236 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

const int LOG = 21;
const int MAX = 2e6 + 15;

int n, m, dp[MAX][LOG], dp2[MAX], depth[MAX], tin[MAX], a[MAX], timer;

vector<int> adj[MAX];
vector<tuple<int, int, int>> queries[MAX];

void dfsInit(int u, int p){
	tin[u] = ++timer;
	dp[u][0] = p; depth[u] = depth[p] + 1;

	for(int i = 1; i < LOG; i++)
		dp[u][i] = dp[ dp[u][i - 1] ][i - 1];

	for(auto v : adj[u]){
		if(v == p) continue;
		dfsInit(v, u);
	}
}

int lca(int u, int v){
	if(depth[u] < depth[v]) swap(u, v);
	int k = depth[u] - depth[v];

	for(int i = LOG - 1; i >= 0; i--)
		if(k & (1 << i)) u = dp[u][i];

	if(u == v) return v;

	for(int i = LOG - 1; i >= 0; i--)
		if(dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];

	return dp[u][0];
}

void dfsCalc(int u, int p){
	vector<pair<int, int>> resps;	

	for(auto v : adj[u]){
		if(v == p) continue;
		dfsCalc(v, u);

		dp2[u] += dp2[v];
		resps.emplace_back(tin[v], dp2[v]);
	}

	a[u] = dp2[u];
	sort(resps.begin(), resps.end());

    int aux = dp2[u];

	for(auto [x, y, w] : queries[u]){
		int curVal = dp2[u] + w;

		while(x != u){ curVal += a[x] - dp2[x]; x = dp[x][0]; }
        while(y != u){ curVal += a[y] - dp2[y]; y = dp[y][0]; }

        aux = max(aux, curVal);
	}
	
	dp2[u] = aux;
}

int32_t main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

    dfsInit(1, 1);

	cin >> m;

	while(m--){
		int u, v, w; cin >> u >> v >> w;
		queries[ lca(u, v) ].emplace_back(u, v, w);
	}	

	dfsCalc(1, 1);

	int ans = 0;

	for(int i = 1; i <= n; i++)
		ans = max(ans, dp2[i]);

	cout << ans << '\n';	
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 10 / 10
• Subtask 6: 0 / 40