oj.uz

Submission #519542

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

using namespace std;

typedef long long ll;

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

struct {
	ll t[(int) 1e6 + 10];

	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 16 ms 24068 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 13 ms 24068 KB Output is correct
4 Correct 16 ms 24280 KB Output is correct
5 Correct 90 ms 40276 KB Output is correct
6 Correct 59 ms 48016 KB Output is correct
7 Correct 79 ms 45324 KB Output is correct
8 Correct 73 ms 39964 KB Output is correct
9 Correct 88 ms 43716 KB Output is correct
10 Correct 64 ms 39960 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24060 KB Output is correct
2 Correct 14 ms 24072 KB Output is correct
3 Correct 14 ms 24336 KB Output is correct
4 Correct 112 ms 51484 KB Output is correct
5 Correct 103 ms 51556 KB Output is correct
6 Correct 108 ms 51628 KB Output is correct
7 Correct 109 ms 51548 KB Output is correct
8 Correct 99 ms 51580 KB Output is correct
9 Correct 104 ms 51552 KB Output is correct
10 Correct 104 ms 51584 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24060 KB Output is correct
2 Correct 14 ms 24072 KB Output is correct
3 Correct 14 ms 24336 KB Output is correct
4 Correct 112 ms 51484 KB Output is correct
5 Correct 103 ms 51556 KB Output is correct
6 Correct 108 ms 51628 KB Output is correct
7 Correct 109 ms 51548 KB Output is correct
8 Correct 99 ms 51580 KB Output is correct
9 Correct 104 ms 51552 KB Output is correct
10 Correct 104 ms 51584 KB Output is correct
11 Correct 21 ms 25264 KB Output is correct
12 Incorrect 97 ms 51492 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 158 ms 43244 KB Output is correct
2 Correct 91 ms 51680 KB Output is correct
3 Correct 168 ms 48536 KB Output is correct
4 Correct 149 ms 42900 KB Output is correct
5 Correct 142 ms 48068 KB Output is correct
6 Correct 125 ms 42980 KB Output is correct
7 Correct 186 ms 47828 KB Output is correct
8 Correct 145 ms 43672 KB Output is correct
9 Correct 97 ms 51560 KB Output is correct
10 Correct 171 ms 46856 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24068 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 13 ms 24068 KB Output is correct
4 Correct 16 ms 24280 KB Output is correct
5 Correct 90 ms 40276 KB Output is correct
6 Correct 59 ms 48016 KB Output is correct
7 Correct 79 ms 45324 KB Output is correct
8 Correct 73 ms 39964 KB Output is correct
9 Correct 88 ms 43716 KB Output is correct
10 Correct 64 ms 39960 KB Output is correct
11 Correct 15 ms 24200 KB Output is correct
12 Correct 14 ms 24340 KB Output is correct
13 Correct 15 ms 24336 KB Output is correct
14 Correct 13 ms 24268 KB Output is correct
15 Correct 16 ms 24208 KB Output is correct
16 Correct 14 ms 24208 KB Output is correct
17 Correct 15 ms 24280 KB Output is correct
18 Correct 14 ms 24272 KB Output is correct
19 Correct 14 ms 24208 KB Output is correct
20 Correct 15 ms 24268 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24068 KB Output is correct
2 Correct 17 ms 24044 KB Output is correct
3 Correct 13 ms 24068 KB Output is correct
4 Correct 16 ms 24280 KB Output is correct
5 Correct 90 ms 40276 KB Output is correct
6 Correct 59 ms 48016 KB Output is correct
7 Correct 79 ms 45324 KB Output is correct
8 Correct 73 ms 39964 KB Output is correct
9 Correct 88 ms 43716 KB Output is correct
10 Correct 64 ms 39960 KB Output is correct
11 Correct 16 ms 24060 KB Output is correct
12 Correct 14 ms 24072 KB Output is correct
13 Correct 14 ms 24336 KB Output is correct
14 Correct 112 ms 51484 KB Output is correct
15 Correct 103 ms 51556 KB Output is correct
16 Correct 108 ms 51628 KB Output is correct
17 Correct 109 ms 51548 KB Output is correct
18 Correct 99 ms 51580 KB Output is correct
19 Correct 104 ms 51552 KB Output is correct
20 Correct 104 ms 51584 KB Output is correct
21 Correct 21 ms 25264 KB Output is correct
22 Incorrect 97 ms 51492 KB Output isn't correct
23 Halted 0 ms 0 KB -