답안 #32083 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32083	2017-09-24T10:57:33 Z	szawinis	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	643 ms	54136 KB

election_campaign

#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];
	}
	assert(anc[u][0] == anc[v][0]);
	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;
	for(int i = 1, u, v; i < n; i++) {
		cin >> u >> v; --u; --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	init_lca(0, -1);
	cin >> m;
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	15464 KB	Output is correct
2	Correct	6 ms	15464 KB	Output is correct
3	Correct	3 ms	15464 KB	Output is correct
4	Correct	3 ms	15596 KB	Output is correct
5	Correct	319 ms	50708 KB	Output is correct
6	Correct	119 ms	45524 KB	Output is correct
7	Correct	269 ms	40680 KB	Output is correct
8	Correct	286 ms	33564 KB	Output is correct
9	Correct	296 ms	39656 KB	Output is correct
10	Correct	336 ms	34100 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	15464 KB	Output is correct
2	Correct	6 ms	15464 KB	Output is correct
3	Correct	0 ms	15596 KB	Output is correct
4	Correct	273 ms	47512 KB	Output is correct
5	Correct	376 ms	47508 KB	Output is correct
6	Correct	249 ms	47636 KB	Output is correct
7	Correct	309 ms	47508 KB	Output is correct
8	Correct	279 ms	47508 KB	Output is correct
9	Correct	259 ms	47636 KB	Output is correct
10	Correct	333 ms	47508 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	15464 KB	Output is correct
2	Correct	6 ms	15464 KB	Output is correct
3	Correct	0 ms	15596 KB	Output is correct
4	Correct	273 ms	47512 KB	Output is correct
5	Correct	376 ms	47508 KB	Output is correct
6	Correct	249 ms	47636 KB	Output is correct
7	Correct	309 ms	47508 KB	Output is correct
8	Correct	279 ms	47508 KB	Output is correct
9	Correct	259 ms	47636 KB	Output is correct
10	Correct	333 ms	47508 KB	Output is correct
11	Correct	19 ms	15992 KB	Output is correct
12	Correct	433 ms	47504 KB	Output is correct
13	Correct	316 ms	47504 KB	Output is correct
14	Correct	299 ms	47640 KB	Output is correct
15	Correct	339 ms	47508 KB	Output is correct
16	Correct	273 ms	47636 KB	Output is correct
17	Correct	363 ms	47504 KB	Output is correct
18	Correct	366 ms	47508 KB	Output is correct
19	Correct	309 ms	47636 KB	Output is correct
20	Correct	426 ms	47504 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	603 ms	54136 KB	Output is correct
2	Correct	266 ms	47636 KB	Output is correct
3	Correct	586 ms	42424 KB	Output is correct
4	Correct	476 ms	35524 KB	Output is correct
5	Correct	439 ms	42160 KB	Output is correct
6	Correct	429 ms	35496 KB	Output is correct
7	Correct	533 ms	41900 KB	Output is correct
8	Correct	563 ms	53380 KB	Output is correct
9	Correct	293 ms	47640 KB	Output is correct
10	Correct	643 ms	41432 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	15464 KB	Output is correct
2	Correct	6 ms	15464 KB	Output is correct
3	Correct	3 ms	15464 KB	Output is correct
4	Correct	3 ms	15596 KB	Output is correct
5	Correct	319 ms	50708 KB	Output is correct
6	Correct	119 ms	45524 KB	Output is correct
7	Correct	269 ms	40680 KB	Output is correct
8	Correct	286 ms	33564 KB	Output is correct
9	Correct	296 ms	39656 KB	Output is correct
10	Correct	336 ms	34100 KB	Output is correct
11	Correct	6 ms	15728 KB	Output is correct
12	Correct	3 ms	15596 KB	Output is correct
13	Correct	6 ms	15596 KB	Output is correct
14	Correct	6 ms	15596 KB	Output is correct
15	Correct	9 ms	15728 KB	Output is correct
16	Correct	3 ms	15596 KB	Output is correct
17	Correct	6 ms	15596 KB	Output is correct
18	Correct	3 ms	15596 KB	Output is correct
19	Correct	9 ms	15596 KB	Output is correct
20	Correct	6 ms	15596 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	15464 KB	Output is correct
2	Correct	6 ms	15464 KB	Output is correct
3	Correct	3 ms	15464 KB	Output is correct
4	Correct	3 ms	15596 KB	Output is correct
5	Correct	319 ms	50708 KB	Output is correct
6	Correct	119 ms	45524 KB	Output is correct
7	Correct	269 ms	40680 KB	Output is correct
8	Correct	286 ms	33564 KB	Output is correct
9	Correct	296 ms	39656 KB	Output is correct
10	Correct	336 ms	34100 KB	Output is correct
11	Correct	9 ms	15464 KB	Output is correct
12	Correct	6 ms	15464 KB	Output is correct
13	Correct	0 ms	15596 KB	Output is correct
14	Correct	273 ms	47512 KB	Output is correct
15	Correct	376 ms	47508 KB	Output is correct
16	Correct	249 ms	47636 KB	Output is correct
17	Correct	309 ms	47508 KB	Output is correct
18	Correct	279 ms	47508 KB	Output is correct
19	Correct	259 ms	47636 KB	Output is correct
20	Correct	333 ms	47508 KB	Output is correct
21	Correct	19 ms	15992 KB	Output is correct
22	Correct	433 ms	47504 KB	Output is correct
23	Correct	316 ms	47504 KB	Output is correct
24	Correct	299 ms	47640 KB	Output is correct
25	Correct	339 ms	47508 KB	Output is correct
26	Correct	273 ms	47636 KB	Output is correct
27	Correct	363 ms	47504 KB	Output is correct
28	Correct	366 ms	47508 KB	Output is correct
29	Correct	309 ms	47636 KB	Output is correct
30	Correct	426 ms	47504 KB	Output is correct
31	Correct	603 ms	54136 KB	Output is correct
32	Correct	266 ms	47636 KB	Output is correct
33	Correct	586 ms	42424 KB	Output is correct
34	Correct	476 ms	35524 KB	Output is correct
35	Correct	439 ms	42160 KB	Output is correct
36	Correct	429 ms	35496 KB	Output is correct
37	Correct	533 ms	41900 KB	Output is correct
38	Correct	563 ms	53380 KB	Output is correct
39	Correct	293 ms	47640 KB	Output is correct
40	Correct	643 ms	41432 KB	Output is correct
41	Correct	6 ms	15728 KB	Output is correct
42	Correct	3 ms	15596 KB	Output is correct
43	Correct	6 ms	15596 KB	Output is correct
44	Correct	6 ms	15596 KB	Output is correct
45	Correct	9 ms	15728 KB	Output is correct
46	Correct	3 ms	15596 KB	Output is correct
47	Correct	6 ms	15596 KB	Output is correct
48	Correct	3 ms	15596 KB	Output is correct
49	Correct	9 ms	15596 KB	Output is correct
50	Correct	6 ms	15596 KB	Output is correct
51	Correct	509 ms	52816 KB	Output is correct
52	Correct	296 ms	47508 KB	Output is correct
53	Correct	536 ms	41492 KB	Output is correct
54	Correct	379 ms	35988 KB	Output is correct
55	Correct	479 ms	53580 KB	Output is correct
56	Correct	476 ms	47508 KB	Output is correct
57	Correct	483 ms	41820 KB	Output is correct
58	Correct	459 ms	35488 KB	Output is correct
59	Correct	469 ms	53676 KB	Output is correct
60	Correct	296 ms	47508 KB	Output is correct
61	Correct	496 ms	41844 KB	Output is correct
62	Correct	403 ms	36352 KB	Output is correct
63	Correct	476 ms	53288 KB	Output is correct
64	Correct	346 ms	47512 KB	Output is correct
65	Correct	553 ms	42036 KB	Output is correct
66	Correct	403 ms	35164 KB	Output is correct
67	Correct	539 ms	54000 KB	Output is correct
68	Correct	413 ms	47508 KB	Output is correct
69	Correct	553 ms	40932 KB	Output is correct
70	Correct	506 ms	34304 KB	Output is correct

답안 #32083

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 30.0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
30.0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
40.0 / 40.0