Submission #947943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947943	2024-03-17T09:35:08 Z	vqpahmad	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	163 ms	83892 KB

election_campaign

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define int long long
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector<int> adj[MAXN];
int fa[MAXN][20], dep[MAXN], dt[MAXN], ft[MAXN], timer = 1;
void dfs(int node, int par){
	dep[node] = dep[par] + 1;
	fa[node][0] = par;
	dt[node] = timer++;
	for (auto to : adj[node]){
		if (to != par) dfs(to, node);
	}
	ft[node] = timer++;
}
int lca(int u, int v){
	if (dep[u] > dep[v]) swap(u, v);
	for (int j = 19; j >= 0; j--){
		if (dep[fa[v][j]] >= dep[u]) v = fa[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; j--){
		if (fa[v][j] != fa[u][j]) v = fa[v][j], u = fa[u][j];
	}
	return fa[u][0];
}
vector<array<int, 3>> queries[MAXN];
ll dp[MAXN];
bool contain(int u, int v){
	return dt[u] <= dt[v] && ft[v] <= ft[u];
}
void solve(int node, int par){
	for (int to : adj[node]){
		if (to != par) {
			solve(to, node);
			dp[node] += dp[to];
		}
	}
	for (auto [u, v, c] : queries[node]){
		ll tm = c;
		for (int to : adj[u]){
			if (contain(to, v) || contain(to, u)) continue;
			tm += dp[to];
		}
		for (int to : adj[v]){
			if (contain(to, v) || contain(to, u)) continue;
			tm += dp[to];
		}
		if (node != u && node != v){
			for (int to : adj[node]){
				if (contain(to, v) || contain(to, u)) continue;
				tm += dp[to];
			}
		}
		ckmax(dp[node], tm);
	}
}
int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1, 1);
	for (int j = 1; j < 20; j++){
		for (int i = 1; i <= n; i++){
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
	int m;
	cin >> m;
	for (int i = 0; i < m; i++){
		int u, v, c;
		cin >> u >> v >> c;
		queries[lca(u, v)].pb({u, v, c});
	}
	solve(1, 1);
	cout << dp[1] << endl;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	49232 KB	Output is correct
2	Correct	21 ms	49148 KB	Output is correct
3	Incorrect	21 ms	49100 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	20 ms	49240 KB	Output is correct
2	Correct	22 ms	49244 KB	Output is correct
3	Correct	23 ms	49636 KB	Output is correct
4	Correct	130 ms	82452 KB	Output is correct
5	Correct	163 ms	80544 KB	Output is correct
6	Correct	139 ms	80728 KB	Output is correct
7	Correct	118 ms	82456 KB	Output is correct
8	Correct	126 ms	82512 KB	Output is correct
9	Correct	131 ms	82564 KB	Output is correct
10	Correct	128 ms	82556 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	49240 KB	Output is correct
2	Correct	22 ms	49244 KB	Output is correct
3	Correct	23 ms	49636 KB	Output is correct
4	Correct	130 ms	82452 KB	Output is correct
5	Correct	163 ms	80544 KB	Output is correct
6	Correct	139 ms	80728 KB	Output is correct
7	Correct	118 ms	82456 KB	Output is correct
8	Correct	126 ms	82512 KB	Output is correct
9	Correct	131 ms	82564 KB	Output is correct
10	Correct	128 ms	82556 KB	Output is correct
11	Correct	32 ms	50516 KB	Output is correct
12	Correct	152 ms	82428 KB	Output is correct
13	Correct	152 ms	82504 KB	Output is correct
14	Correct	133 ms	80736 KB	Output is correct
15	Correct	136 ms	82560 KB	Output is correct
16	Correct	135 ms	80540 KB	Output is correct
17	Correct	135 ms	82588 KB	Output is correct
18	Correct	145 ms	82540 KB	Output is correct
19	Correct	125 ms	82516 KB	Output is correct
20	Correct	142 ms	83892 KB	Output is correct