Submission #160229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
160229	2019-10-26T10:52:46 Z	iefnah06	Election Campaign (JOI15_election_campaign)	C++11	10 / 100	190 ms	30428 KB

election_campaign

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1.1e5;
const int MAXM = 1.1e5;
int N, M;
vector<int> adj[MAXN];

int par[MAXN][20];
int depth[MAXN];

void dfs_par(int cur, int prv) {
	if (prv) {
		adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv));
	}
	par[cur][0] = prv;
	for (int i = 0; par[cur][i]; i++) {
		par[cur][i+1] = par[par[cur][i]][i];
	}
	for (int nxt : adj[cur]) {
		depth[nxt] = depth[cur] + 1;
		dfs_par(nxt, cur);
	}
}

int lift(int a, int d) {
	assert(d >= 0);
	for (int i = 0; (1 << i) <= d; i++) {
		if (d & (1 << i)) {
			a = par[a][i];
		}
	}
	return a;
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	a = lift(a, depth[a] - depth[b]);
	assert(depth[a] == depth[b]);
	if (a == b) return a;
	int i = 0;
	while (par[a][i]) i++;
	while (i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	assert(a != b);
	assert(par[a][0] == par[b][0]);
	return par[a][0];
}

int getchild(int a, int b) {
	assert(depth[a] < depth[b]);
	int c = lift(b, depth[b] - depth[a] - 1);
	assert(par[c][0] == a);
	return c;
}

vector<array<int, 3>> paths[MAXN];
int dp[MAXN];
int chsum[MAXN];

int dfs(int cur) {
	for (int nxt : adj[cur]) {
		chsum[cur] += dfs(nxt);
	}
	int ans = chsum[cur];
	for (auto it : paths[cur]) {
		int val = chsum[cur] + it[2];
		if (cur != it[0]) {
			val += chsum[it[0]];
			val -= dp[getchild(cur, it[0])];
		}
		assert(cur != it[1]);
		val += chsum[it[1]];
		val -= dp[getchild(cur, it[1])];
		ans = max(ans, val);
	}
	return dp[cur] = ans;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs_par(1, 0);
	cin >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (depth[a] > depth[b]) swap(a, b);
		paths[lca(a, b)].push_back({a, b, c});
	}
	
	int ans = dfs(1);
	cout << ans << '\n';

	return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5628 KB	Output is correct
2	Correct	6 ms	5496 KB	Output is correct
3	Incorrect	7 ms	5496 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5496 KB	Output is correct
2	Correct	6 ms	5624 KB	Output is correct
3	Correct	8 ms	5752 KB	Output is correct
4	Correct	157 ms	29916 KB	Output is correct
5	Correct	148 ms	29916 KB	Output is correct
6	Correct	138 ms	30048 KB	Output is correct
7	Correct	158 ms	30036 KB	Output is correct
8	Correct	149 ms	30072 KB	Output is correct
9	Correct	127 ms	29972 KB	Output is correct
10	Correct	147 ms	29944 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5496 KB	Output is correct
2	Correct	6 ms	5624 KB	Output is correct
3	Correct	8 ms	5752 KB	Output is correct
4	Correct	157 ms	29916 KB	Output is correct
5	Correct	148 ms	29916 KB	Output is correct
6	Correct	138 ms	30048 KB	Output is correct
7	Correct	158 ms	30036 KB	Output is correct
8	Correct	149 ms	30072 KB	Output is correct
9	Correct	127 ms	29972 KB	Output is correct
10	Correct	147 ms	29944 KB	Output is correct
11	Correct	18 ms	6520 KB	Output is correct
12	Correct	169 ms	30300 KB	Output is correct
13	Correct	154 ms	30272 KB	Output is correct
14	Correct	141 ms	30296 KB	Output is correct
15	Correct	190 ms	30428 KB	Output is correct
16	Correct	135 ms	30200 KB	Output is correct
17	Correct	147 ms	30232 KB	Output is correct
18	Correct	161 ms	30384 KB	Output is correct
19	Correct	132 ms	30328 KB	Output is correct
20	Correct	157 ms	30328 KB	Output is correct