oj.uz

Submission #776438

# Submission time Handle Problem Language Result Execution time Memory
776438 2023-07-07T22:00:23 Z Hacv16 Election Campaign (JOI15_election_campaign) C++17
0 / 100
 153 ms 109140 KB 
#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());

	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]; }

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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94380 KB Output is correct
2 Incorrect 38 ms 94180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 94164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 94164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 109140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94380 KB Output is correct
2 Incorrect 38 ms 94180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94380 KB Output is correct
2 Incorrect 38 ms 94180 KB Output isn't correct
3 Halted 0 ms 0 KB -