oj.uz

Submission #32935

# Submission time Handle Problem Language Result Execution time Memory
32935 2017-10-17T16:29:03 Z aome Election Campaign (JOI15_election_campaign) C++14
10 / 100
 483 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) {
	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
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 Incorrect 129 ms 23052 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 0 ms 19752 KB Output is correct
4 Correct 299 ms 34152 KB Output is correct
5 Correct 303 ms 34152 KB Output is correct
6 Correct 263 ms 34148 KB Output is correct
7 Correct 303 ms 34148 KB Output is correct
8 Correct 299 ms 34148 KB Output is correct
9 Correct 269 ms 34148 KB Output is correct
10 Correct 299 ms 34152 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 0 ms 19752 KB Output is correct
4 Correct 299 ms 34152 KB Output is correct
5 Correct 303 ms 34152 KB Output is correct
6 Correct 263 ms 34148 KB Output is correct
7 Correct 303 ms 34148 KB Output is correct
8 Correct 299 ms 34148 KB Output is correct
9 Correct 269 ms 34148 KB Output is correct
10 Correct 299 ms 34152 KB Output is correct
11 Correct 16 ms 20280 KB Output is correct
12 Correct 256 ms 34148 KB Output is correct
13 Correct 309 ms 34152 KB Output is correct
14 Correct 253 ms 34152 KB Output is correct
15 Correct 296 ms 34148 KB Output is correct
16 Correct 253 ms 34148 KB Output is correct
17 Correct 323 ms 34148 KB Output is correct
18 Correct 269 ms 34144 KB Output is correct
19 Correct 263 ms 34148 KB Output is correct
20 Correct 256 ms 34148 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 483 ms 24748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 129 ms 23052 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 129 ms 23052 KB Output isn't correct
6 Halted 0 ms 0 KB -