답안 #87781 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87781	2018-12-02T13:50:06 Z	MB81	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	955 ms	161648 KB

election_campaign

// Ala be zekrellah tatmaenolgholoob ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define MP make_pair
const int maxn = 2e5+9;
const int lg = 19;
const ll mod = 1e9+7;

vector <int> g[maxn];
vector <pair<pii,int>> vec[maxn], edge[maxn];
int n, m;
int par[maxn][lg], sum[maxn][lg], sub[maxn], h[maxn], curchild[maxn], dp[maxn];

int lca (int v, int u) {
	if (h[v] < h[u]) swap(v, u);
	for (int i = lg - 1; i >= 0; i--)
		if (par[v][i] + 1 && h[par[v][i]] >= h[u])
			v = par[v][i];
	if (v == u)
		return v;
	for (int i = lg - 1; i >= 0; i--)
		if (par[v][i] != par[u][i]) {
			v = par[v][i];
			u = par[u][i];
		}
	return par[v][0];
}

int get (int v, int u) {
	int res = 0;
	for (int i = lg - 1; i >= 0; i--)
		if (par[v][i] + 1 && h[par[v][i]] >= h[u]) {
			res += sum[v][i];
			v = par[v][i];
		}
	return res;
}

void dfs0 (int v, int parent = -1) {
	par[v][0] = parent;
	if (parent + 1) {
		h[v] = h[parent] + 1;
		vec[parent].push_back( MP( MP( v, 0 ), v ) );
	}
	for (int i = 1; i < lg; i++)
		if (par[v][i - 1] + 1) {
			par[v][i] = par[par[v][i - 1]][i - 1];
			if (par[v][i] + 1)
			vec[par[v][i]].push_back( MP( MP( v, i ), curchild[par[v][i]]) );
		}
	for (auto u : g[v]) {
		if (u == parent) continue;
		curchild[v] = u;
		dfs0(u, v);
	}
	return;
}

void dfs (int v, int parent = -1) {
	for (auto u : g[v]) {
	    if (u == parent) continue;
		dfs(u, v);
		sub[v] += dp[u];
	}
	for (auto x : vec[v]) {
		int u = x.F.F, depth = x.F.S, firstchild = x.S;
		sum[u][depth] = 1LL * get(u, firstchild) + sub[v] - dp[firstchild];
	}
	dp[v] = sub[v];
	for (auto e : edge[v]) {
		int x = e.F.F, y = e.F.S, c = e.S;
		if (x == v || y == v) {
			if (y == v) swap(x, y);
			dp[v] = max(1LL * dp[v], 1LL * get(y, v) + sub[y] + c);
		}
		else
			dp[v] = max(1LL * dp[v], 1LL * get(x, v) + get(y, v) - sub[v] + sub[x] + sub[y] + c);
	}
	return;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
	    int v, u;
	    cin >> v >> u;
		--v; --u;
		g[v].push_back( u );
		g[u].push_back( v );
	}
	memset(par, -1, sizeof par);
	dfs0(0);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int v, u, c;
		cin >> v >> u >> c;
		--v, --u;
		edge[lca(v, u)].push_back( MP( MP( v, u ), c ) );
	}
	dfs(0);
	cout << dp[0] << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	29304 KB	Output is correct
2	Correct	29 ms	29432 KB	Output is correct
3	Correct	29 ms	29520 KB	Output is correct
4	Correct	52 ms	29720 KB	Output is correct
5	Correct	287 ms	50352 KB	Output is correct
6	Correct	304 ms	78704 KB	Output is correct
7	Correct	572 ms	78704 KB	Output is correct
8	Correct	156 ms	78704 KB	Output is correct
9	Correct	513 ms	78704 KB	Output is correct
10	Correct	164 ms	78704 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	78704 KB	Output is correct
2	Correct	31 ms	78704 KB	Output is correct
3	Correct	34 ms	78704 KB	Output is correct
4	Correct	463 ms	87740 KB	Output is correct
5	Correct	439 ms	90176 KB	Output is correct
6	Correct	470 ms	92892 KB	Output is correct
7	Correct	445 ms	95216 KB	Output is correct
8	Correct	426 ms	97540 KB	Output is correct
9	Correct	416 ms	100112 KB	Output is correct
10	Correct	476 ms	102500 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	78704 KB	Output is correct
2	Correct	31 ms	78704 KB	Output is correct
3	Correct	34 ms	78704 KB	Output is correct
4	Correct	463 ms	87740 KB	Output is correct
5	Correct	439 ms	90176 KB	Output is correct
6	Correct	470 ms	92892 KB	Output is correct
7	Correct	445 ms	95216 KB	Output is correct
8	Correct	426 ms	97540 KB	Output is correct
9	Correct	416 ms	100112 KB	Output is correct
10	Correct	476 ms	102500 KB	Output is correct
11	Correct	42 ms	102500 KB	Output is correct
12	Correct	526 ms	105472 KB	Output is correct
13	Correct	563 ms	108424 KB	Output is correct
14	Correct	576 ms	111044 KB	Output is correct
15	Correct	571 ms	113760 KB	Output is correct
16	Correct	538 ms	116528 KB	Output is correct
17	Correct	609 ms	119308 KB	Output is correct
18	Correct	617 ms	122068 KB	Output is correct
19	Correct	598 ms	124704 KB	Output is correct
20	Correct	534 ms	127436 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	329 ms	127436 KB	Output is correct
2	Correct	470 ms	132360 KB	Output is correct
3	Correct	761 ms	132360 KB	Output is correct
4	Correct	243 ms	132360 KB	Output is correct
5	Correct	848 ms	134840 KB	Output is correct
6	Correct	233 ms	134840 KB	Output is correct
7	Correct	864 ms	139376 KB	Output is correct
8	Correct	445 ms	139376 KB	Output is correct
9	Correct	564 ms	149268 KB	Output is correct
10	Correct	955 ms	149268 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	29304 KB	Output is correct
2	Correct	29 ms	29432 KB	Output is correct
3	Correct	29 ms	29520 KB	Output is correct
4	Correct	52 ms	29720 KB	Output is correct
5	Correct	287 ms	50352 KB	Output is correct
6	Correct	304 ms	78704 KB	Output is correct
7	Correct	572 ms	78704 KB	Output is correct
8	Correct	156 ms	78704 KB	Output is correct
9	Correct	513 ms	78704 KB	Output is correct
10	Correct	164 ms	78704 KB	Output is correct
11	Correct	34 ms	149268 KB	Output is correct
12	Correct	28 ms	149268 KB	Output is correct
13	Correct	34 ms	149268 KB	Output is correct
14	Correct	30 ms	149268 KB	Output is correct
15	Correct	28 ms	149268 KB	Output is correct
16	Correct	40 ms	149268 KB	Output is correct
17	Correct	28 ms	149268 KB	Output is correct
18	Correct	30 ms	149268 KB	Output is correct
19	Correct	29 ms	149268 KB	Output is correct
20	Correct	33 ms	149268 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	29304 KB	Output is correct
2	Correct	29 ms	29432 KB	Output is correct
3	Correct	29 ms	29520 KB	Output is correct
4	Correct	52 ms	29720 KB	Output is correct
5	Correct	287 ms	50352 KB	Output is correct
6	Correct	304 ms	78704 KB	Output is correct
7	Correct	572 ms	78704 KB	Output is correct
8	Correct	156 ms	78704 KB	Output is correct
9	Correct	513 ms	78704 KB	Output is correct
10	Correct	164 ms	78704 KB	Output is correct
11	Correct	28 ms	78704 KB	Output is correct
12	Correct	31 ms	78704 KB	Output is correct
13	Correct	34 ms	78704 KB	Output is correct
14	Correct	463 ms	87740 KB	Output is correct
15	Correct	439 ms	90176 KB	Output is correct
16	Correct	470 ms	92892 KB	Output is correct
17	Correct	445 ms	95216 KB	Output is correct
18	Correct	426 ms	97540 KB	Output is correct
19	Correct	416 ms	100112 KB	Output is correct
20	Correct	476 ms	102500 KB	Output is correct
21	Correct	42 ms	102500 KB	Output is correct
22	Correct	526 ms	105472 KB	Output is correct
23	Correct	563 ms	108424 KB	Output is correct
24	Correct	576 ms	111044 KB	Output is correct
25	Correct	571 ms	113760 KB	Output is correct
26	Correct	538 ms	116528 KB	Output is correct
27	Correct	609 ms	119308 KB	Output is correct
28	Correct	617 ms	122068 KB	Output is correct
29	Correct	598 ms	124704 KB	Output is correct
30	Correct	534 ms	127436 KB	Output is correct
31	Correct	329 ms	127436 KB	Output is correct
32	Correct	470 ms	132360 KB	Output is correct
33	Correct	761 ms	132360 KB	Output is correct
34	Correct	243 ms	132360 KB	Output is correct
35	Correct	848 ms	134840 KB	Output is correct
36	Correct	233 ms	134840 KB	Output is correct
37	Correct	864 ms	139376 KB	Output is correct
38	Correct	445 ms	139376 KB	Output is correct
39	Correct	564 ms	149268 KB	Output is correct
40	Correct	955 ms	149268 KB	Output is correct
41	Correct	34 ms	149268 KB	Output is correct
42	Correct	28 ms	149268 KB	Output is correct
43	Correct	34 ms	149268 KB	Output is correct
44	Correct	30 ms	149268 KB	Output is correct
45	Correct	28 ms	149268 KB	Output is correct
46	Correct	40 ms	149268 KB	Output is correct
47	Correct	28 ms	149268 KB	Output is correct
48	Correct	30 ms	149268 KB	Output is correct
49	Correct	29 ms	149268 KB	Output is correct
50	Correct	33 ms	149268 KB	Output is correct
51	Correct	445 ms	149268 KB	Output is correct
52	Correct	512 ms	157076 KB	Output is correct
53	Correct	865 ms	157076 KB	Output is correct
54	Correct	279 ms	157076 KB	Output is correct
55	Correct	405 ms	157076 KB	Output is correct
56	Correct	497 ms	161648 KB	Output is correct
57	Correct	871 ms	161648 KB	Output is correct
58	Correct	257 ms	161648 KB	Output is correct
59	Correct	355 ms	161648 KB	Output is correct
60	Correct	468 ms	161648 KB	Output is correct
61	Correct	714 ms	161648 KB	Output is correct
62	Correct	210 ms	161648 KB	Output is correct
63	Correct	343 ms	161648 KB	Output is correct
64	Correct	454 ms	161648 KB	Output is correct
65	Correct	776 ms	161648 KB	Output is correct
66	Correct	213 ms	161648 KB	Output is correct
67	Correct	338 ms	161648 KB	Output is correct
68	Correct	441 ms	161648 KB	Output is correct
69	Correct	826 ms	161648 KB	Output is correct
70	Correct	262 ms	161648 KB	Output is correct

답안 #87781

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