oj.uz

Submission #87781

# Submission time Handle Problem Language Result Execution time Memory
87781 2018-12-02T13:50:06 Z MB81 Election Campaign (JOI15_election_campaign) C++17
100 / 100
 955 ms 161648 KB 
// 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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