Submission #753281

# Submission time Handle Problem Language Result Execution time Memory
753281 2023-06-05T02:16:41 Z LeonaRaging Election Campaign (JOI15_election_campaign) C++14
10 / 100
121 ms 36276 KB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const int maxn = 1e5 + 4;
const int N = 16;

struct Query {
	int u, v, w;
	Query(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
} q[maxn];

int n, m, h[maxn], tin[maxn], tout[maxn], up[maxn][20], dp[maxn], sum[maxn];
vector<int> adj[maxn], cross[maxn], down[maxn];

void dfs1(int u, int p) {
	tin[u] = ++tin[0];
	for (int j = 1; j <= N; j++)
		up[u][j] = up[up[u][j - 1]][j - 1];
	for (int v : adj[u])
		if (v != p) {
			h[v] = h[u] + 1;
			up[v][0] = u;
			dfs1(v, u);
		}
	tout[u] = tin[0];
}

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

int jump(int u, int v) {
	for (int j = N; j >= 0; j--)
		if (up[u][j] && !isPar(v, up[u][j]))
			u = up[u][j];
	return u;
}

void dfs2(int u, int p) {
	for (int v : adj[u]) if (v != p) {
		dfs2(v, u);
		sum[u] += dp[v];
	}
	dp[u] = sum[u];
	for (int i : cross[u]) {
		int a = q[i].u, b = q[i].v, w = q[i].w;
		dp[u] = max(dp[u], sum[u] - dp[jump(a, u)] - dp[jump(b, u)] + sum[a] + sum[b] + w);
	}
	for (int i : down[u]) {
		int v = q[i].v, w = q[i].w;
		dp[u] = max(dp[u], sum[u] - dp[jump(v, u)] + sum[v] + w);
	}
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
    	cin >> u >> v;
    	adj[u].pb(v);
    	adj[v].pb(u);
    }
    dfs1(1, 0);
    cin >> m;
    for (int i = 1, u, v, w; i <= m; i++) {
    	cin >> u >> v >> w;
    	if (h[u] > h[v]) swap(u, v);
    	if (isPar(v, u)) 
    		down[u].pb(i);
    	else 
    		cross[up[jump(u, v)][0]].pb(i);
    	q[i] = Query(u, v, w);
    }
    dfs2(1, 0);
    cout << dp[1];
}

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8556 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Incorrect 4 ms 8552 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 8520 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 5 ms 8788 KB Output is correct
4 Correct 117 ms 35916 KB Output is correct
5 Correct 110 ms 35916 KB Output is correct
6 Correct 103 ms 36044 KB Output is correct
7 Correct 109 ms 35892 KB Output is correct
8 Correct 115 ms 35916 KB Output is correct
9 Correct 96 ms 35972 KB Output is correct
10 Correct 100 ms 35824 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 8520 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 5 ms 8788 KB Output is correct
4 Correct 117 ms 35916 KB Output is correct
5 Correct 110 ms 35916 KB Output is correct
6 Correct 103 ms 36044 KB Output is correct
7 Correct 109 ms 35892 KB Output is correct
8 Correct 115 ms 35916 KB Output is correct
9 Correct 96 ms 35972 KB Output is correct
10 Correct 100 ms 35824 KB Output is correct
11 Correct 13 ms 9252 KB Output is correct
12 Correct 116 ms 36184 KB Output is correct
13 Correct 115 ms 36128 KB Output is correct
14 Correct 100 ms 36216 KB Output is correct
15 Correct 120 ms 36168 KB Output is correct
16 Correct 96 ms 36240 KB Output is correct
17 Correct 106 ms 36276 KB Output is correct
18 Correct 102 ms 36180 KB Output is correct
19 Correct 96 ms 36240 KB Output is correct
20 Correct 115 ms 36116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 24560 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 8556 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Incorrect 4 ms 8552 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 8556 KB Output is correct
2 Correct 5 ms 8532 KB Output is correct
3 Incorrect 4 ms 8552 KB Output isn't correct
4 Halted 0 ms 0 KB -