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
#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]);
}
# 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 -
# 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
# 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
# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 21280 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 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 -
# 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 -