oj.uz

Submission #32936

# Submission time Handle Problem Language Result Execution time Memory
32936 2017-10-17T16:38:47 Z aome Election Campaign (JOI15_election_campaign) C++14
100 / 100
 959 ms 34152 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Go {
	int u, v, w;

	Go (int u, int v, int w) :
		u(u), v(v), w(w) {}
};

int n, m, cnt;
int st[N], ed[N];
int h[N], p[20][N];
int f[2][N];
int it[4 * N];
int lazy[4 * N];
vector<int> G[N];
vector<Go> go[N];

void dfs(int u) {
	st[u] = ++cnt;
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		p[0][v] = u, h[v] = h[u] + 1, dfs(v);
	}
	ed[u] = cnt;
}

void push(int i, int l, int r) {
	if (!lazy[i]) return;
	if (l == r) it[i] += lazy[i];
	else lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0;
}

void upd(int i, int l, int r, int u, int v, int x) {
	push(i, l, r);
	if (l > v || u > r) return;
	if (u <= l && r <= v) {
		lazy[i] = x, push(i, l, r); return;
	}
	int mid = (l + r) >> 1;
	upd(i << 1, l, mid, u, v, x);
	upd(i << 1 | 1, mid + 1, r, u, v, x);
}

int get(int i, int l, int r, int p) {
	push(i, l, r);
	if (l == r) return it[i];
	int mid = (l + r) >> 1;
	if (mid >= p) return get(i << 1, l, mid, p);
	return get(i << 1 | 1, mid + 1, r, p);
}

void solve(int u) {
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		solve(v), f[0][u] += f[1][v];
	}
	f[1][u] = f[0][u];
	for (auto i : go[u]) {
		int cur = f[0][u] + i.w;
		if (i.u != u) {
			int x = i.u;
			for (int i = 17; i >= 0; --i) {
				if (h[p[i][x]] > h[u]) x = p[i][x];
			}
			cur += get(1, 1, n, st[i.u]) + f[0][i.u] - f[1][x];
		}
		if (i.v != u) {
			int x = i.v;
			for (int i = 17; i >= 0; --i) {
				if (h[p[i][x]] > h[u]) x = p[i][x];
			}
			cur += get(1, 1, n, st[i.v]) + f[0][i.v] - f[1][x];
		}
		f[1][u] = max(f[1][u], cur);
	}
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		upd(1, 1, n, st[v], ed[v], f[0][u] - f[1][v]);
	}
}

int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 17; i >= 0; --i) {
		if (h[p[i][v]] >= h[u]) v = p[i][v];
	}
	for (int i = 17; i >= 0; --i) {
		if (p[i][v] != p[i][u]) v = p[i][v], u = p[i][u];
	}
	return (u == v) ? u : p[0][u];
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < (n - 1); ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	p[0][1] = h[1] = 1, dfs(1);
	for (int i = 1; i <= 17; ++i) {
		for (int j = 1; j <= n; ++j) {
			p[i][j] = p[i - 1][p[i - 1][j]];
		}
	}
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		go[lca(u, v)].push_back(Go(u, v, w));
	}
	solve(1); cout << f[1][1] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19752 KB Output is correct
2 Correct 0 ms 19752 KB Output is correct
3 Correct 0 ms 19752 KB Output is correct
4 Correct 0 ms 19752 KB Output is correct
5 Correct 176 ms 23052 KB Output is correct
6 Correct 76 ms 32036 KB Output is correct
7 Correct 183 ms 28796 KB Output is correct
8 Correct 106 ms 23464 KB Output is correct
9 Correct 103 ms 26940 KB Output is correct
10 Correct 116 ms 23472 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19752 KB Output is correct
2 Correct 3 ms 19752 KB Output is correct
3 Correct 6 ms 19752 KB Output is correct
4 Correct 349 ms 34152 KB Output is correct
5 Correct 356 ms 34148 KB Output is correct
6 Correct 366 ms 34148 KB Output is correct
7 Correct 459 ms 34144 KB Output is correct
8 Correct 453 ms 34152 KB Output is correct
9 Correct 243 ms 34148 KB Output is correct
10 Correct 436 ms 34148 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19752 KB Output is correct
2 Correct 3 ms 19752 KB Output is correct
3 Correct 6 ms 19752 KB Output is correct
4 Correct 349 ms 34152 KB Output is correct
5 Correct 356 ms 34148 KB Output is correct
6 Correct 366 ms 34148 KB Output is correct
7 Correct 459 ms 34144 KB Output is correct
8 Correct 453 ms 34152 KB Output is correct
9 Correct 243 ms 34148 KB Output is correct
10 Correct 436 ms 34148 KB Output is correct
11 Correct 23 ms 20280 KB Output is correct
12 Correct 303 ms 34144 KB Output is correct
13 Correct 296 ms 34152 KB Output is correct
14 Correct 376 ms 34152 KB Output is correct
15 Correct 273 ms 34148 KB Output is correct
16 Correct 376 ms 34152 KB Output is correct
17 Correct 286 ms 34152 KB Output is correct
18 Correct 439 ms 34148 KB Output is correct
19 Correct 346 ms 34148 KB Output is correct
20 Correct 309 ms 34152 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 24748 KB Output is correct
2 Correct 436 ms 34152 KB Output is correct
3 Correct 879 ms 30508 KB Output is correct
4 Correct 679 ms 25468 KB Output is correct
5 Correct 929 ms 29944 KB Output is correct
6 Correct 463 ms 25804 KB Output is correct
7 Correct 796 ms 29580 KB Output is correct
8 Correct 843 ms 24832 KB Output is correct
9 Correct 266 ms 34152 KB Output is correct
10 Correct 786 ms 28668 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19752 KB Output is correct
2 Correct 0 ms 19752 KB Output is correct
3 Correct 0 ms 19752 KB Output is correct
4 Correct 0 ms 19752 KB Output is correct
5 Correct 176 ms 23052 KB Output is correct
6 Correct 76 ms 32036 KB Output is correct
7 Correct 183 ms 28796 KB Output is correct
8 Correct 106 ms 23464 KB Output is correct
9 Correct 103 ms 26940 KB Output is correct
10 Correct 116 ms 23472 KB Output is correct
11 Correct 0 ms 19752 KB Output is correct
12 Correct 3 ms 19752 KB Output is correct
13 Correct 3 ms 19752 KB Output is correct
14 Correct 0 ms 19752 KB Output is correct
15 Correct 0 ms 19752 KB Output is correct
16 Correct 0 ms 19752 KB Output is correct
17 Correct 0 ms 19752 KB Output is correct
18 Correct 0 ms 19752 KB Output is correct
19 Correct 3 ms 19752 KB Output is correct
20 Correct 0 ms 19752 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19752 KB Output is correct
2 Correct 0 ms 19752 KB Output is correct
3 Correct 0 ms 19752 KB Output is correct
4 Correct 0 ms 19752 KB Output is correct
5 Correct 176 ms 23052 KB Output is correct
6 Correct 76 ms 32036 KB Output is correct
7 Correct 183 ms 28796 KB Output is correct
8 Correct 106 ms 23464 KB Output is correct
9 Correct 103 ms 26940 KB Output is correct
10 Correct 116 ms 23472 KB Output is correct
11 Correct 0 ms 19752 KB Output is correct
12 Correct 3 ms 19752 KB Output is correct
13 Correct 6 ms 19752 KB Output is correct
14 Correct 349 ms 34152 KB Output is correct
15 Correct 356 ms 34148 KB Output is correct
16 Correct 366 ms 34148 KB Output is correct
17 Correct 459 ms 34144 KB Output is correct
18 Correct 453 ms 34152 KB Output is correct
19 Correct 243 ms 34148 KB Output is correct
20 Correct 436 ms 34148 KB Output is correct
21 Correct 23 ms 20280 KB Output is correct
22 Correct 303 ms 34144 KB Output is correct
23 Correct 296 ms 34152 KB Output is correct
24 Correct 376 ms 34152 KB Output is correct
25 Correct 273 ms 34148 KB Output is correct
26 Correct 376 ms 34152 KB Output is correct
27 Correct 286 ms 34152 KB Output is correct
28 Correct 439 ms 34148 KB Output is correct
29 Correct 346 ms 34148 KB Output is correct
30 Correct 309 ms 34152 KB Output is correct
31 Correct 879 ms 24748 KB Output is correct
32 Correct 436 ms 34152 KB Output is correct
33 Correct 879 ms 30508 KB Output is correct
34 Correct 679 ms 25468 KB Output is correct
35 Correct 929 ms 29944 KB Output is correct
36 Correct 463 ms 25804 KB Output is correct
37 Correct 796 ms 29580 KB Output is correct
38 Correct 843 ms 24832 KB Output is correct
39 Correct 266 ms 34152 KB Output is correct
40 Correct 786 ms 28668 KB Output is correct
41 Correct 0 ms 19752 KB Output is correct
42 Correct 3 ms 19752 KB Output is correct
43 Correct 3 ms 19752 KB Output is correct
44 Correct 0 ms 19752 KB Output is correct
45 Correct 0 ms 19752 KB Output is correct
46 Correct 0 ms 19752 KB Output is correct
47 Correct 0 ms 19752 KB Output is correct
48 Correct 0 ms 19752 KB Output is correct
49 Correct 3 ms 19752 KB Output is correct
50 Correct 0 ms 19752 KB Output is correct
51 Correct 663 ms 24744 KB Output is correct
52 Correct 269 ms 34148 KB Output is correct
53 Correct 813 ms 28816 KB Output is correct
54 Correct 596 ms 25272 KB Output is correct
55 Correct 869 ms 24976 KB Output is correct
56 Correct 376 ms 34152 KB Output is correct
57 Correct 913 ms 29252 KB Output is correct
58 Correct 479 ms 25300 KB Output is correct
59 Correct 783 ms 24808 KB Output is correct
60 Correct 296 ms 34152 KB Output is correct
61 Correct 726 ms 29496 KB Output is correct
62 Correct 349 ms 25896 KB Output is correct
63 Correct 506 ms 25044 KB Output is correct
64 Correct 329 ms 34152 KB Output is correct
65 Correct 676 ms 29664 KB Output is correct
66 Correct 543 ms 25504 KB Output is correct
67 Correct 899 ms 25464 KB Output is correct
68 Correct 426 ms 34148 KB Output is correct
69 Correct 959 ms 27884 KB Output is correct
70 Correct 483 ms 25568 KB Output is correct