답안 #88138 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88138	2018-12-04T00:32:08 Z	KCSC	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	503 ms	99328 KB

election_campaign

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

const int LOG = 19;
const int DIM = 200005;

int bit[DIM], anc[DIM][LOG], dp[DIM], aux[DIM], lev[DIM], fst[DIM], lst[DIM];
vector<tuple<int, int, int>> lis[DIM]; vector<int> edg[DIM];

void update(int p, int x) {
	for (; p < DIM; p += (p & -p)) {
		bit[p] += x; } }

int query(int p, int x = 0) {
	for (; p > 0; p -= (p & -p)) {
		x += bit[p]; } 
	return x; }

int lca(int x, int y) {
	if (lev[x] > lev[y]) {
		swap(x, y); }
	for (int i = LOG - 1; i >= 0; --i) {
		if (lev[y] - (1 << i) >= lev[x]) {
			y = anc[y][i]; } }
	for (int i = LOG - 1; i >= 0; --i) {		
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i]; y = anc[y][i]; } }
	return (x == y ? x : anc[x][0]); }

void dfs1(int x, int f) {
	static int nr = 0;
	fst[x] = ++nr; lev[x] = lev[f] + 1; anc[x][0] = f;
	for (int i = 1; i < LOG; ++i) {
		anc[x][i] = anc[anc[x][i - 1]][i - 1]; }
	for (int y : edg[x]) {
		if (y != f) {
			dfs1(y, x); } } 
	lst[x] = ++nr; }

void dfs2(int x, int f) {
	for (int y : edg[x]) {
		if (y != f) {
			dfs2(y, x); aux[x] += dp[y]; } }
	dp[x] = aux[x];
	for (auto &tp : lis[x]) {
		int l, r, c; tie(l, r, c) = tp;
		dp[x] = max(dp[x], query(fst[l]) + query(fst[r]) + aux[x] + c); }
	update(fst[x], aux[x] - dp[x]); update(lst[x], dp[x] - aux[x]); }	

int main(void) {
#ifdef HOME
	freopen("election.in", "r", stdin);
	freopen("election.out", "w", stdout); 
#endif
	int n; cin >> n;
	for (int i = 1; i < n; ++i) {
		int x, y; cin >> x >> y;
		edg[x].push_back(y); edg[y].push_back(x); }
	dfs1(1, 0); int m; cin >> m;
	while (m--) {
		int x, y, c; cin >> x >> y >> c;
		lis[lca(x, y)].emplace_back(x, y, c); }
	dfs2(1, 0); cout << dp[1] << "\n";
	return 0; }

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9848 KB	Output is correct
2	Correct	13 ms	9856 KB	Output is correct
3	Correct	10 ms	9920 KB	Output is correct
4	Correct	11 ms	9968 KB	Output is correct
5	Correct	176 ms	24580 KB	Output is correct
6	Correct	128 ms	33364 KB	Output is correct
7	Correct	172 ms	33364 KB	Output is correct
8	Correct	152 ms	33364 KB	Output is correct
9	Correct	177 ms	33364 KB	Output is correct
10	Correct	147 ms	33364 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	33364 KB	Output is correct
2	Correct	10 ms	33364 KB	Output is correct
3	Correct	12 ms	33364 KB	Output is correct
4	Correct	325 ms	42536 KB	Output is correct
5	Correct	344 ms	45052 KB	Output is correct
6	Correct	327 ms	47548 KB	Output is correct
7	Correct	350 ms	49872 KB	Output is correct
8	Correct	330 ms	52324 KB	Output is correct
9	Correct	340 ms	54948 KB	Output is correct
10	Correct	317 ms	57248 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	33364 KB	Output is correct
2	Correct	10 ms	33364 KB	Output is correct
3	Correct	12 ms	33364 KB	Output is correct
4	Correct	325 ms	42536 KB	Output is correct
5	Correct	344 ms	45052 KB	Output is correct
6	Correct	327 ms	47548 KB	Output is correct
7	Correct	350 ms	49872 KB	Output is correct
8	Correct	330 ms	52324 KB	Output is correct
9	Correct	340 ms	54948 KB	Output is correct
10	Correct	317 ms	57248 KB	Output is correct
11	Correct	39 ms	57248 KB	Output is correct
12	Correct	346 ms	60492 KB	Output is correct
13	Correct	359 ms	62992 KB	Output is correct
14	Correct	324 ms	65844 KB	Output is correct
15	Correct	347 ms	68540 KB	Output is correct
16	Correct	322 ms	71268 KB	Output is correct
17	Correct	354 ms	74036 KB	Output is correct
18	Correct	336 ms	76864 KB	Output is correct
19	Correct	288 ms	77512 KB	Output is correct
20	Correct	291 ms	77548 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	311 ms	77548 KB	Output is correct
2	Correct	284 ms	77548 KB	Output is correct
3	Correct	423 ms	77548 KB	Output is correct
4	Correct	319 ms	77548 KB	Output is correct
5	Correct	439 ms	77548 KB	Output is correct
6	Correct	313 ms	77548 KB	Output is correct
7	Correct	503 ms	77548 KB	Output is correct
8	Correct	422 ms	77548 KB	Output is correct
9	Correct	292 ms	77708 KB	Output is correct
10	Correct	405 ms	77708 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9848 KB	Output is correct
2	Correct	13 ms	9856 KB	Output is correct
3	Correct	10 ms	9920 KB	Output is correct
4	Correct	11 ms	9968 KB	Output is correct
5	Correct	176 ms	24580 KB	Output is correct
6	Correct	128 ms	33364 KB	Output is correct
7	Correct	172 ms	33364 KB	Output is correct
8	Correct	152 ms	33364 KB	Output is correct
9	Correct	177 ms	33364 KB	Output is correct
10	Correct	147 ms	33364 KB	Output is correct
11	Correct	12 ms	77708 KB	Output is correct
12	Correct	14 ms	77708 KB	Output is correct
13	Correct	12 ms	77708 KB	Output is correct
14	Correct	12 ms	77708 KB	Output is correct
15	Correct	12 ms	77708 KB	Output is correct
16	Correct	14 ms	77708 KB	Output is correct
17	Correct	13 ms	77708 KB	Output is correct
18	Correct	13 ms	77708 KB	Output is correct
19	Correct	14 ms	77708 KB	Output is correct
20	Correct	14 ms	77708 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9848 KB	Output is correct
2	Correct	13 ms	9856 KB	Output is correct
3	Correct	10 ms	9920 KB	Output is correct
4	Correct	11 ms	9968 KB	Output is correct
5	Correct	176 ms	24580 KB	Output is correct
6	Correct	128 ms	33364 KB	Output is correct
7	Correct	172 ms	33364 KB	Output is correct
8	Correct	152 ms	33364 KB	Output is correct
9	Correct	177 ms	33364 KB	Output is correct
10	Correct	147 ms	33364 KB	Output is correct
11	Correct	11 ms	33364 KB	Output is correct
12	Correct	10 ms	33364 KB	Output is correct
13	Correct	12 ms	33364 KB	Output is correct
14	Correct	325 ms	42536 KB	Output is correct
15	Correct	344 ms	45052 KB	Output is correct
16	Correct	327 ms	47548 KB	Output is correct
17	Correct	350 ms	49872 KB	Output is correct
18	Correct	330 ms	52324 KB	Output is correct
19	Correct	340 ms	54948 KB	Output is correct
20	Correct	317 ms	57248 KB	Output is correct
21	Correct	39 ms	57248 KB	Output is correct
22	Correct	346 ms	60492 KB	Output is correct
23	Correct	359 ms	62992 KB	Output is correct
24	Correct	324 ms	65844 KB	Output is correct
25	Correct	347 ms	68540 KB	Output is correct
26	Correct	322 ms	71268 KB	Output is correct
27	Correct	354 ms	74036 KB	Output is correct
28	Correct	336 ms	76864 KB	Output is correct
29	Correct	288 ms	77512 KB	Output is correct
30	Correct	291 ms	77548 KB	Output is correct
31	Correct	311 ms	77548 KB	Output is correct
32	Correct	284 ms	77548 KB	Output is correct
33	Correct	423 ms	77548 KB	Output is correct
34	Correct	319 ms	77548 KB	Output is correct
35	Correct	439 ms	77548 KB	Output is correct
36	Correct	313 ms	77548 KB	Output is correct
37	Correct	503 ms	77548 KB	Output is correct
38	Correct	422 ms	77548 KB	Output is correct
39	Correct	292 ms	77708 KB	Output is correct
40	Correct	405 ms	77708 KB	Output is correct
41	Correct	12 ms	77708 KB	Output is correct
42	Correct	14 ms	77708 KB	Output is correct
43	Correct	12 ms	77708 KB	Output is correct
44	Correct	12 ms	77708 KB	Output is correct
45	Correct	12 ms	77708 KB	Output is correct
46	Correct	14 ms	77708 KB	Output is correct
47	Correct	13 ms	77708 KB	Output is correct
48	Correct	13 ms	77708 KB	Output is correct
49	Correct	14 ms	77708 KB	Output is correct
50	Correct	14 ms	77708 KB	Output is correct
51	Correct	414 ms	77708 KB	Output is correct
52	Correct	348 ms	78044 KB	Output is correct
53	Correct	462 ms	78044 KB	Output is correct
54	Correct	294 ms	78044 KB	Output is correct
55	Correct	340 ms	78044 KB	Output is correct
56	Correct	295 ms	84616 KB	Output is correct
57	Correct	453 ms	84616 KB	Output is correct
58	Correct	313 ms	84616 KB	Output is correct
59	Correct	391 ms	84868 KB	Output is correct
60	Correct	360 ms	95636 KB	Output is correct
61	Correct	422 ms	95636 KB	Output is correct
62	Correct	310 ms	95636 KB	Output is correct
63	Correct	402 ms	95636 KB	Output is correct
64	Correct	370 ms	99328 KB	Output is correct
65	Correct	479 ms	99328 KB	Output is correct
66	Correct	319 ms	99328 KB	Output is correct
67	Correct	372 ms	99328 KB	Output is correct
68	Correct	332 ms	99328 KB	Output is correct
69	Correct	385 ms	99328 KB	Output is correct
70	Correct	294 ms	99328 KB	Output is correct

답안 #88138

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