oj.uz

Submission #776439

# Submission time Handle Problem Language Result Execution time Memory
776439 2023-07-07T22:04:07 Z Hacv16 Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 122236 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());

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

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94228 KB Output is correct
2 Correct 46 ms 94276 KB Output is correct
3 Correct 47 ms 94244 KB Output is correct
4 Correct 46 ms 94360 KB Output is correct
5 Correct 99 ms 107864 KB Output is correct
6 Correct 89 ms 120216 KB Output is correct
7 Correct 121 ms 115792 KB Output is correct
8 Correct 97 ms 108428 KB Output is correct
9 Correct 125 ms 113740 KB Output is correct
10 Correct 90 ms 108420 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94156 KB Output is correct
2 Correct 47 ms 94256 KB Output is correct
3 Correct 48 ms 94480 KB Output is correct
4 Execution timed out 1071 ms 122236 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94156 KB Output is correct
2 Correct 47 ms 94256 KB Output is correct
3 Correct 48 ms 94480 KB Output is correct
4 Execution timed out 1071 ms 122236 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 108732 KB Output is correct
2 Execution timed out 1097 ms 122104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94228 KB Output is correct
2 Correct 46 ms 94276 KB Output is correct
3 Correct 47 ms 94244 KB Output is correct
4 Correct 46 ms 94360 KB Output is correct
5 Correct 99 ms 107864 KB Output is correct
6 Correct 89 ms 120216 KB Output is correct
7 Correct 121 ms 115792 KB Output is correct
8 Correct 97 ms 108428 KB Output is correct
9 Correct 125 ms 113740 KB Output is correct
10 Correct 90 ms 108420 KB Output is correct
11 Correct 48 ms 94412 KB Output is correct
12 Correct 48 ms 94668 KB Output is correct
13 Correct 49 ms 94480 KB Output is correct
14 Correct 49 ms 94388 KB Output is correct
15 Correct 47 ms 94412 KB Output is correct
16 Correct 47 ms 94396 KB Output is correct
17 Correct 48 ms 94380 KB Output is correct
18 Correct 48 ms 94532 KB Output is correct
19 Correct 48 ms 94344 KB Output is correct
20 Correct 49 ms 94564 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 94228 KB Output is correct
2 Correct 46 ms 94276 KB Output is correct
3 Correct 47 ms 94244 KB Output is correct
4 Correct 46 ms 94360 KB Output is correct
5 Correct 99 ms 107864 KB Output is correct
6 Correct 89 ms 120216 KB Output is correct
7 Correct 121 ms 115792 KB Output is correct
8 Correct 97 ms 108428 KB Output is correct
9 Correct 125 ms 113740 KB Output is correct
10 Correct 90 ms 108420 KB Output is correct
11 Correct 46 ms 94156 KB Output is correct
12 Correct 47 ms 94256 KB Output is correct
13 Correct 48 ms 94480 KB Output is correct
14 Execution timed out 1071 ms 122236 KB Time limit exceeded
15 Halted 0 ms 0 KB -