oj.uz

Submission #519540

# Submission time Handle Problem Language Result Execution time Memory
519540 2022-01-26T15:27:55 Z valerikk Election Campaign (JOI15_election_campaign) C++17
55 / 100
 184 ms 51020 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;
const int K = 20;

struct {
	ll t[N];

	void upd(int ind, ll val) {
		for (int i = ind + 1; i < N; i += i & -i) {
			t[i] += val;
		}
	}

	void upd(int l, int r, ll val) {
		upd(l, val);
		upd(r, -val);
	}

	int get(int ind) {
		ll sum = 0;
		for (int i = ind + 1; i > 0; i -= i & -i) {
			sum += t[i];
		}
		return sum;
	}
} fsum, fdp;

int n;
vector<int> g[N];
int m;
int a[N], b[N];
ll c[N];

int tin[N], tout[N];
int par[N];
int up[K][N];

void dfs(int v, int p) {
	static int t = 0;
	tin[v] = t++;
	par[v] = p;

	if (p != v) {
		g[v].erase(find(g[v].begin(), g[v].end(), p));
	}

	for (int u : g[v]) {
		dfs(u, v);
	}
	
	tout[v] = t;
}

bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}

int getlca(int v, int u) {
	if (anc(v, u)) {
		return v;
	}
	if (anc(u, v)) {
		return u;
	}

	for (int i = K - 1; i >= 0; i--) {
		if (!anc(up[i][v], u)) {
			v = up[i][v];
		}
	}
	return par[v];
}

vector<int> by_lca[N];
ll dp[N];
ll sum[N];

void dfsdp(int v) {
	for (int u : g[v]) {
		dfsdp(u);
		sum[v] += dp[u];
	}

	dp[v] = sum[v];
	for (int i : by_lca[v]) {
		ll cur = fsum.get(tin[a[i]]) + fsum.get(tin[b[i]]) + sum[v] - fdp.get(tin[a[i]]) - fdp.get(tin[b[i]]) + c[i];
		dp[v] = max(dp[v], cur);
	}

	fsum.upd(tin[v], tout[v], sum[v]);
	fdp.upd(tin[v], tout[v], dp[v]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;
		b[i]--;
	}

	dfs(0, 0);

	for (int i = 0; i < n; i++) {
		up[0][i] = par[i];
	}
	for (int i = 1; i < K; i++) {
		for (int j = 0; j < n; j++) {
			up[i][j] = up[i - 1][up[i - 1][j]];
		}
	}

	for (int i = 0; i < m; i++) {
		by_lca[getlca(a[i], b[i])].push_back(i);
	}

	dfsdp(0);

	cout << dp[0] << "\n";

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24012 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 14 ms 24076 KB Output is correct
4 Correct 13 ms 24268 KB Output is correct
5 Correct 85 ms 40576 KB Output is correct
6 Correct 57 ms 48268 KB Output is correct
7 Correct 78 ms 45524 KB Output is correct
8 Correct 81 ms 40244 KB Output is correct
9 Correct 79 ms 43916 KB Output is correct
10 Correct 61 ms 40240 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 13 ms 24288 KB Output is correct
4 Correct 91 ms 50936 KB Output is correct
5 Correct 92 ms 50936 KB Output is correct
6 Correct 95 ms 50872 KB Output is correct
7 Correct 96 ms 50936 KB Output is correct
8 Correct 93 ms 50872 KB Output is correct
9 Correct 92 ms 50884 KB Output is correct
10 Correct 94 ms 51020 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 13 ms 24288 KB Output is correct
4 Correct 91 ms 50936 KB Output is correct
5 Correct 92 ms 50936 KB Output is correct
6 Correct 95 ms 50872 KB Output is correct
7 Correct 96 ms 50936 KB Output is correct
8 Correct 93 ms 50872 KB Output is correct
9 Correct 92 ms 50884 KB Output is correct
10 Correct 94 ms 51020 KB Output is correct
11 Correct 19 ms 25180 KB Output is correct
12 Incorrect 97 ms 50848 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 42660 KB Output is correct
2 Correct 115 ms 50956 KB Output is correct
3 Correct 184 ms 47780 KB Output is correct
4 Correct 133 ms 42248 KB Output is correct
5 Correct 146 ms 47404 KB Output is correct
6 Correct 130 ms 42356 KB Output is correct
7 Correct 164 ms 47152 KB Output is correct
8 Correct 145 ms 43244 KB Output is correct
9 Correct 89 ms 50884 KB Output is correct
10 Correct 166 ms 46232 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24012 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 14 ms 24076 KB Output is correct
4 Correct 13 ms 24268 KB Output is correct
5 Correct 85 ms 40576 KB Output is correct
6 Correct 57 ms 48268 KB Output is correct
7 Correct 78 ms 45524 KB Output is correct
8 Correct 81 ms 40244 KB Output is correct
9 Correct 79 ms 43916 KB Output is correct
10 Correct 61 ms 40240 KB Output is correct
11 Correct 14 ms 24192 KB Output is correct
12 Correct 14 ms 24288 KB Output is correct
13 Correct 13 ms 24340 KB Output is correct
14 Correct 14 ms 24268 KB Output is correct
15 Correct 13 ms 24204 KB Output is correct
16 Correct 14 ms 24232 KB Output is correct
17 Correct 14 ms 24268 KB Output is correct
18 Correct 17 ms 24308 KB Output is correct
19 Correct 14 ms 24268 KB Output is correct
20 Correct 13 ms 24268 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24012 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 14 ms 24076 KB Output is correct
4 Correct 13 ms 24268 KB Output is correct
5 Correct 85 ms 40576 KB Output is correct
6 Correct 57 ms 48268 KB Output is correct
7 Correct 78 ms 45524 KB Output is correct
8 Correct 81 ms 40244 KB Output is correct
9 Correct 79 ms 43916 KB Output is correct
10 Correct 61 ms 40240 KB Output is correct
11 Correct 14 ms 24012 KB Output is correct
12 Correct 13 ms 24012 KB Output is correct
13 Correct 13 ms 24288 KB Output is correct
14 Correct 91 ms 50936 KB Output is correct
15 Correct 92 ms 50936 KB Output is correct
16 Correct 95 ms 50872 KB Output is correct
17 Correct 96 ms 50936 KB Output is correct
18 Correct 93 ms 50872 KB Output is correct
19 Correct 92 ms 50884 KB Output is correct
20 Correct 94 ms 51020 KB Output is correct
21 Correct 19 ms 25180 KB Output is correct
22 Incorrect 97 ms 50848 KB Output isn't correct
23 Halted 0 ms 0 KB -