답안 #160237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160237	2019-10-26T11:30:43 Z	iefnah06	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	304 ms	29688 KB

election_campaign

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1.1e5;
int N, M;
vector<int> adj[MAXN];

int par[MAXN][20];
int depth[MAXN];

void dfs_par(int cur, int prv) {
	if (prv) {
		adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv));
	}
	par[cur][0] = prv;
	for (int i = 0; par[cur][i]; i++) {
		par[cur][i+1] = par[par[cur][i]][i];
	}
	for (int nxt : adj[cur]) {
		depth[nxt] = depth[cur] + 1;
		dfs_par(nxt, cur);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	int d = depth[a] - depth[b];
	for (int i = 0; (1 << i) <= d; i++) {
		if (d & (1 << i)) {
			a = par[a][i];
		}
	}
	assert(depth[a] == depth[b]);
	if (a == b) return a;
	int i = 0;
	while (par[a][i]) i++;
	while (i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	assert(par[a][0] == par[b][0]);
	assert(a != b);
	return par[a][0];
}

struct bit {
	int a[MAXN];

	bit() {
		memset(a, 0, sizeof(a));
	}

	void update(int i, int v) {
		for (i++; i <= N; i += (i & -i)) {
			a[i] += v;
		}
	}

	void update(int l, int r, int v) { // half open
		update(l, +v);
		update(r, -v);
	}

	int query(int i) { // value at i-th position
		int ans = 0;
		for (i++; i; i -= (i & -i)) {
			ans += a[i];
		}
		return ans;
	}
} bestsum, chsum;

vector<array<int, 3>> paths[MAXN];
int st[MAXN];
int en[MAXN];
int curind = 0;

int dfs(int cur) {
	st[cur] = curind++;
	int ch = 0;
	for (int nxt : adj[cur]) {
		ch += dfs(nxt);
	}
	en[cur] = curind;

	int best = ch;
	for (auto it : paths[cur]) {
		int val = ch + it[2];
		if (it[0] != cur) {
			val -= bestsum.query(st[it[0]]);
			val += chsum.query(st[it[0]]);
		}
		assert(it[1] != cur);
		val -= bestsum.query(st[it[1]]);
		val += chsum.query(st[it[1]]);
		best = max(best, val);
	}
	bestsum.update(st[cur], en[cur], best);
	chsum.update(st[cur], en[cur], ch);

	return best;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs_par(1, 0);

	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (depth[a] > depth[b]) swap(a, b);
		paths[lca(a, b)].push_back({a, b, c});
	}

	cout << dfs(1) << '\n';

	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6392 KB	Output is correct
2	Correct	7 ms	6392 KB	Output is correct
3	Correct	8 ms	6392 KB	Output is correct
4	Correct	7 ms	6520 KB	Output is correct
5	Correct	103 ms	19832 KB	Output is correct
6	Correct	68 ms	25976 KB	Output is correct
7	Correct	105 ms	23800 KB	Output is correct
8	Correct	77 ms	20216 KB	Output is correct
9	Correct	105 ms	22520 KB	Output is correct
10	Correct	74 ms	20216 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6392 KB	Output is correct
2	Correct	7 ms	6392 KB	Output is correct
3	Correct	7 ms	6520 KB	Output is correct
4	Correct	139 ms	26716 KB	Output is correct
5	Correct	142 ms	26744 KB	Output is correct
6	Correct	135 ms	26872 KB	Output is correct
7	Correct	146 ms	26744 KB	Output is correct
8	Correct	153 ms	26736 KB	Output is correct
9	Correct	124 ms	26872 KB	Output is correct
10	Correct	137 ms	26744 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6392 KB	Output is correct
2	Correct	7 ms	6392 KB	Output is correct
3	Correct	7 ms	6520 KB	Output is correct
4	Correct	139 ms	26716 KB	Output is correct
5	Correct	142 ms	26744 KB	Output is correct
6	Correct	135 ms	26872 KB	Output is correct
7	Correct	146 ms	26744 KB	Output is correct
8	Correct	153 ms	26736 KB	Output is correct
9	Correct	124 ms	26872 KB	Output is correct
10	Correct	137 ms	26744 KB	Output is correct
11	Correct	18 ms	7032 KB	Output is correct
12	Correct	140 ms	26752 KB	Output is correct
13	Correct	139 ms	26744 KB	Output is correct
14	Correct	139 ms	26792 KB	Output is correct
15	Correct	161 ms	26880 KB	Output is correct
16	Correct	141 ms	26888 KB	Output is correct
17	Correct	145 ms	26744 KB	Output is correct
18	Correct	162 ms	26780 KB	Output is correct
19	Correct	130 ms	26872 KB	Output is correct
20	Correct	144 ms	26868 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	150 ms	20140 KB	Output is correct
2	Correct	126 ms	29176 KB	Output is correct
3	Correct	237 ms	26744 KB	Output is correct
4	Correct	129 ms	23088 KB	Output is correct
5	Correct	218 ms	26576 KB	Output is correct
6	Correct	136 ms	23020 KB	Output is correct
7	Correct	304 ms	26124 KB	Output is correct
8	Correct	184 ms	22940 KB	Output is correct
9	Correct	136 ms	29256 KB	Output is correct
10	Correct	253 ms	25352 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6392 KB	Output is correct
2	Correct	7 ms	6392 KB	Output is correct
3	Correct	8 ms	6392 KB	Output is correct
4	Correct	7 ms	6520 KB	Output is correct
5	Correct	103 ms	19832 KB	Output is correct
6	Correct	68 ms	25976 KB	Output is correct
7	Correct	105 ms	23800 KB	Output is correct
8	Correct	77 ms	20216 KB	Output is correct
9	Correct	105 ms	22520 KB	Output is correct
10	Correct	74 ms	20216 KB	Output is correct
11	Correct	8 ms	6520 KB	Output is correct
12	Correct	8 ms	6648 KB	Output is correct
13	Correct	8 ms	6648 KB	Output is correct
14	Correct	9 ms	6648 KB	Output is correct
15	Correct	9 ms	6520 KB	Output is correct
16	Correct	8 ms	6520 KB	Output is correct
17	Correct	9 ms	6520 KB	Output is correct
18	Correct	8 ms	6648 KB	Output is correct
19	Correct	8 ms	6520 KB	Output is correct
20	Correct	9 ms	6648 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	6392 KB	Output is correct
2	Correct	7 ms	6392 KB	Output is correct
3	Correct	8 ms	6392 KB	Output is correct
4	Correct	7 ms	6520 KB	Output is correct
5	Correct	103 ms	19832 KB	Output is correct
6	Correct	68 ms	25976 KB	Output is correct
7	Correct	105 ms	23800 KB	Output is correct
8	Correct	77 ms	20216 KB	Output is correct
9	Correct	105 ms	22520 KB	Output is correct
10	Correct	74 ms	20216 KB	Output is correct
11	Correct	7 ms	6392 KB	Output is correct
12	Correct	7 ms	6392 KB	Output is correct
13	Correct	7 ms	6520 KB	Output is correct
14	Correct	139 ms	26716 KB	Output is correct
15	Correct	142 ms	26744 KB	Output is correct
16	Correct	135 ms	26872 KB	Output is correct
17	Correct	146 ms	26744 KB	Output is correct
18	Correct	153 ms	26736 KB	Output is correct
19	Correct	124 ms	26872 KB	Output is correct
20	Correct	137 ms	26744 KB	Output is correct
21	Correct	18 ms	7032 KB	Output is correct
22	Correct	140 ms	26752 KB	Output is correct
23	Correct	139 ms	26744 KB	Output is correct
24	Correct	139 ms	26792 KB	Output is correct
25	Correct	161 ms	26880 KB	Output is correct
26	Correct	141 ms	26888 KB	Output is correct
27	Correct	145 ms	26744 KB	Output is correct
28	Correct	162 ms	26780 KB	Output is correct
29	Correct	130 ms	26872 KB	Output is correct
30	Correct	144 ms	26868 KB	Output is correct
31	Correct	150 ms	20140 KB	Output is correct
32	Correct	126 ms	29176 KB	Output is correct
33	Correct	237 ms	26744 KB	Output is correct
34	Correct	129 ms	23088 KB	Output is correct
35	Correct	218 ms	26576 KB	Output is correct
36	Correct	136 ms	23020 KB	Output is correct
37	Correct	304 ms	26124 KB	Output is correct
38	Correct	184 ms	22940 KB	Output is correct
39	Correct	136 ms	29256 KB	Output is correct
40	Correct	253 ms	25352 KB	Output is correct
41	Correct	8 ms	6520 KB	Output is correct
42	Correct	8 ms	6648 KB	Output is correct
43	Correct	8 ms	6648 KB	Output is correct
44	Correct	9 ms	6648 KB	Output is correct
45	Correct	9 ms	6520 KB	Output is correct
46	Correct	8 ms	6520 KB	Output is correct
47	Correct	9 ms	6520 KB	Output is correct
48	Correct	8 ms	6648 KB	Output is correct
49	Correct	8 ms	6520 KB	Output is correct
50	Correct	9 ms	6648 KB	Output is correct
51	Correct	174 ms	23260 KB	Output is correct
52	Correct	151 ms	29688 KB	Output is correct
53	Correct	229 ms	25648 KB	Output is correct
54	Correct	127 ms	23348 KB	Output is correct
55	Correct	166 ms	22904 KB	Output is correct
56	Correct	148 ms	29548 KB	Output is correct
57	Correct	216 ms	26364 KB	Output is correct
58	Correct	133 ms	23304 KB	Output is correct
59	Correct	161 ms	23160 KB	Output is correct
60	Correct	146 ms	29560 KB	Output is correct
61	Correct	194 ms	26376 KB	Output is correct
62	Correct	136 ms	23252 KB	Output is correct
63	Correct	174 ms	23012 KB	Output is correct
64	Correct	144 ms	29560 KB	Output is correct
65	Correct	248 ms	26260 KB	Output is correct
66	Correct	130 ms	23476 KB	Output is correct
67	Correct	174 ms	22888 KB	Output is correct
68	Correct	144 ms	29560 KB	Output is correct
69	Correct	214 ms	25436 KB	Output is correct
70	Correct	134 ms	23516 KB	Output is correct

답안 #160237

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