oj.uz

Submission #59211

# Submission time Handle Problem Language Result Execution time Memory
59211 2018-07-21T06:58:51 Z gusfring Election Campaign (JOI15_election_campaign) C++14
30 / 100
 468 ms 95540 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e5)+1;
 
int n, m;
vector<int> g[MAX];
vector<tuple<int,int,int> > paths[MAX];
 
int d[MAX];
vector<int> anc[MAX];
void init_lca(int u, int p) {
	for(int v: g[u]) if(v != p) {
		d[v] = d[u] + 1;
		anc[v].push_back(u);
		for(int j = 0; 1 << j+1 <= d[v]; j++)
			anc[v].push_back(anc[anc[v][j]][j]);
		init_lca(v, u);
	}
}
int query_lca(int u, int v) {
	if(d[u] > d[v]) {
		int diff = d[u] - d[v];
		for(int j = anc[u].size()-1; j >= 0; j--) if(diff >> j & 1) u = anc[u][j];
	} else if(d[u] < d[v]) {
		int diff = d[v] - d[u];
		for(int j = anc[v].size()-1; j >= 0; j--) if(diff >> j & 1) v = anc[v][j];
	}
	if(u == v) return u;
	for(int j = anc[u].size()-1; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j]) {
		u = anc[u][j];
		v = anc[v][j];
	}
	return anc[u][0];
}
 
int dp[MAX], sum[MAX], c[MAX];
map<int, int> mpf[MAX];
void dfs(int u, int p) {
	for(int v: g[u]) if(v != p) {
		dfs(v, u);
		sum[u] += dp[v];
		if(mpf[v].size() > mpf[u].size()) {
			mpf[u].swap(mpf[v]);
			swap(c[u], c[v]);
		}
		for(auto pp: mpf[v]) mpf[u][pp.first] = pp.second + c[v] - c[u];
	}
	dp[u] = sum[u];
	for(auto path: paths[u]) {
		int a, b, w;
		tie(a, b, w) = path;
		int down1 = (a != u ? mpf[u][a] + c[u] : 0);
		int down2 = (b != u ? mpf[u][b] + c[u] : 0);
		dp[u] = max(sum[u] + down1 + down2 + w, dp[u]);
	}
	mpf[u][u] = -c[u];
	c[u] += sum[u] - dp[u];
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	bool ok = true;
	for(int i = 1, u, v; i < n; i++) {
		cin >> u >> v; --u; --v;
		if(u != v - 1) ok = false;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	init_lca(0, -1);
	cin >> m;
	if(n > 10000 && m > 10000 && !ok) return 0;
	for(int i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w; --u; --v;
		paths[query_lca(u, v)].emplace_back(u, v, w);
	}
	dfs(0, -1);
	cout << dp[0];
}

Compilation message

election_campaign.cpp: In function 'void init_lca(int, int)':
election_campaign.cpp:15:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(int j = 0; 1 << j+1 <= d[v]; j++)
                       ~^~
election_campaign.cpp: In function 'int query_lca(int, int)':
election_campaign.cpp:29:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = anc[u].size()-1; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j]) {
                                               ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Correct 15 ms 12264 KB Output is correct
3 Correct 15 ms 12372 KB Output is correct
4 Correct 16 ms 12540 KB Output is correct
5 Correct 468 ms 50740 KB Output is correct
6 Correct 143 ms 50740 KB Output is correct
7 Correct 354 ms 50740 KB Output is correct
8 Correct 301 ms 50740 KB Output is correct
9 Correct 442 ms 50740 KB Output is correct
10 Correct 335 ms 50740 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 50740 KB Output is correct
2 Correct 15 ms 50740 KB Output is correct
3 Correct 16 ms 50740 KB Output is correct
4 Correct 253 ms 55884 KB Output is correct
5 Correct 404 ms 58372 KB Output is correct
6 Correct 226 ms 60796 KB Output is correct
7 Correct 306 ms 63384 KB Output is correct
8 Correct 290 ms 65756 KB Output is correct
9 Correct 400 ms 68288 KB Output is correct
10 Correct 433 ms 70612 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 50740 KB Output is correct
2 Correct 15 ms 50740 KB Output is correct
3 Correct 16 ms 50740 KB Output is correct
4 Correct 253 ms 55884 KB Output is correct
5 Correct 404 ms 58372 KB Output is correct
6 Correct 226 ms 60796 KB Output is correct
7 Correct 306 ms 63384 KB Output is correct
8 Correct 290 ms 65756 KB Output is correct
9 Correct 400 ms 68288 KB Output is correct
10 Correct 433 ms 70612 KB Output is correct
11 Correct 29 ms 70612 KB Output is correct
12 Correct 288 ms 73636 KB Output is correct
13 Correct 380 ms 76420 KB Output is correct
14 Correct 272 ms 79172 KB Output is correct
15 Correct 318 ms 81864 KB Output is correct
16 Correct 290 ms 84728 KB Output is correct
17 Correct 319 ms 87328 KB Output is correct
18 Correct 377 ms 90224 KB Output is correct
19 Correct 253 ms 92912 KB Output is correct
20 Correct 292 ms 95540 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Correct 15 ms 12264 KB Output is correct
3 Correct 15 ms 12372 KB Output is correct
4 Correct 16 ms 12540 KB Output is correct
5 Correct 468 ms 50740 KB Output is correct
6 Correct 143 ms 50740 KB Output is correct
7 Correct 354 ms 50740 KB Output is correct
8 Correct 301 ms 50740 KB Output is correct
9 Correct 442 ms 50740 KB Output is correct
10 Correct 335 ms 50740 KB Output is correct
11 Correct 18 ms 95540 KB Output is correct
12 Correct 14 ms 95540 KB Output is correct
13 Correct 15 ms 95540 KB Output is correct
14 Correct 15 ms 95540 KB Output is correct
15 Correct 18 ms 95540 KB Output is correct
16 Correct 13 ms 95540 KB Output is correct
17 Correct 16 ms 95540 KB Output is correct
18 Correct 18 ms 95540 KB Output is correct
19 Correct 16 ms 95540 KB Output is correct
20 Correct 18 ms 95540 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12152 KB Output is correct
2 Correct 15 ms 12264 KB Output is correct
3 Correct 15 ms 12372 KB Output is correct
4 Correct 16 ms 12540 KB Output is correct
5 Correct 468 ms 50740 KB Output is correct
6 Correct 143 ms 50740 KB Output is correct
7 Correct 354 ms 50740 KB Output is correct
8 Correct 301 ms 50740 KB Output is correct
9 Correct 442 ms 50740 KB Output is correct
10 Correct 335 ms 50740 KB Output is correct
11 Correct 15 ms 50740 KB Output is correct
12 Correct 15 ms 50740 KB Output is correct
13 Correct 16 ms 50740 KB Output is correct
14 Correct 253 ms 55884 KB Output is correct
15 Correct 404 ms 58372 KB Output is correct
16 Correct 226 ms 60796 KB Output is correct
17 Correct 306 ms 63384 KB Output is correct
18 Correct 290 ms 65756 KB Output is correct
19 Correct 400 ms 68288 KB Output is correct
20 Correct 433 ms 70612 KB Output is correct
21 Correct 29 ms 70612 KB Output is correct
22 Correct 288 ms 73636 KB Output is correct
23 Correct 380 ms 76420 KB Output is correct
24 Correct 272 ms 79172 KB Output is correct
25 Correct 318 ms 81864 KB Output is correct
26 Correct 290 ms 84728 KB Output is correct
27 Correct 319 ms 87328 KB Output is correct
28 Correct 377 ms 90224 KB Output is correct
29 Correct 253 ms 92912 KB Output is correct
30 Correct 292 ms 95540 KB Output is correct
31 Incorrect 119 ms 95540 KB Output isn't correct
32 Halted 0 ms 0 KB -