Submission #754991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754991	2023-06-09T08:22:22 Z	jmyszka2007	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	137 ms	29980 KB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define pb push_back
constexpr int LIM = 1e5;
vector<int>g[LIM + 10];
int pre[LIM + 10];
int post[LIM + 10];
int nxt[LIM + 10][18];
int dp[LIM + 10][2];
vector<pair<pi, pi> >zap[LIM + 10];
bool czy(int a, int b) {
	return pre[a] <= pre[b] && post[a] >= post[b];
}
pi lca(int a, int b) {
	if(pre[a] <= pre[b]) {
		swap(a, b);
	}
	for(int i = 17; i >= 0; i--) {
		if(!czy(nxt[a][i], b)) {
			a = nxt[a][i];
		}
	}
	return {a, nxt[a][0]};
}
int aktpre = 1, aktpost = 1;
void dfs(int v, int o) {
	pre[v] = aktpre++;
	nxt[v][0] = o;
	for(int i = 1; i <= 17; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
	}
	for(auto x : g[v]) {
		if(x != o) {
			dfs(x, v);
		}
	}
	post[v] = aktpost++;
}
void cntdp(int v, int o) {
	int sum = 0;
	for(auto x : g[v]) {
		if(x != o) {
			cntdp(x, v);
			sum += max(dp[x][0], dp[x][1]);
		}
	}
	dp[v][0] = sum;
	for(auto x : zap[v]) {
		if(x.nd.st == v) {
			dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.nd][0] + x.st.st);
		}
		else if(x.nd.nd == v) {
			dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.st][0] + x.st.st);
		}
		else {
			dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.nd][0] + dp[x.nd.st][0] + x.st.st);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1);
	int t;
	cin >> t;
	for(int i = 1; i <= t; i++) {
		int a, b, x;
		cin >> a >> b >> x;
		pi tmp = lca(a, b);
		zap[tmp.nd].pb({{x, tmp.st}, {a, b}});
	}
	cntdp(1, 1);
	cout << max(dp[1][0], dp[1][1]);
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	4 ms	4948 KB	Output is correct
3	Incorrect	4 ms	5028 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	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	4 ms	5204 KB	Output is correct
4	Correct	117 ms	29492 KB	Output is correct
5	Correct	124 ms	29528 KB	Output is correct
6	Correct	106 ms	29508 KB	Output is correct
7	Correct	118 ms	29476 KB	Output is correct
8	Correct	119 ms	29588 KB	Output is correct
9	Correct	109 ms	29608 KB	Output is correct
10	Correct	108 ms	29516 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	4 ms	5204 KB	Output is correct
4	Correct	117 ms	29492 KB	Output is correct
5	Correct	124 ms	29528 KB	Output is correct
6	Correct	106 ms	29508 KB	Output is correct
7	Correct	118 ms	29476 KB	Output is correct
8	Correct	119 ms	29588 KB	Output is correct
9	Correct	109 ms	29608 KB	Output is correct
10	Correct	108 ms	29516 KB	Output is correct
11	Correct	14 ms	6100 KB	Output is correct
12	Correct	133 ms	29740 KB	Output is correct
13	Correct	127 ms	29848 KB	Output is correct
14	Correct	119 ms	29916 KB	Output is correct
15	Correct	137 ms	29820 KB	Output is correct
16	Correct	119 ms	29980 KB	Output is correct
17	Correct	111 ms	29848 KB	Output is correct
18	Correct	115 ms	29856 KB	Output is correct
19	Correct	117 ms	29860 KB	Output is correct
20	Correct	111 ms	29804 KB	Output is correct