답안 #59211 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59211	2018-07-21T06:58:51 Z	gusfring	Election Campaign (JOI15_election_campaign)	C++14	30 / 100	468 ms	95540 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];
	}
	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	119 ms	95540 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #59211

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
0 / 40.0