Submission #947942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947942	2024-03-17T09:34:37 Z	vqpahmad	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	144 ms	82640 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;
}

Compilation message

election_campaign.cpp: In function 'void solve(long long int, long long int)':
election_campaign.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |  for (auto [u, v, c] : queries[node]){
      |            ^

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	49328 KB	Output is correct
2	Correct	21 ms	49244 KB	Output is correct
3	Incorrect	21 ms	49240 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	21 ms	49240 KB	Output is correct
2	Correct	21 ms	49244 KB	Output is correct
3	Correct	21 ms	49500 KB	Output is correct
4	Correct	123 ms	82512 KB	Output is correct
5	Correct	117 ms	82512 KB	Output is correct
6	Correct	113 ms	82516 KB	Output is correct
7	Correct	118 ms	82492 KB	Output is correct
8	Correct	119 ms	82564 KB	Output is correct
9	Correct	113 ms	82448 KB	Output is correct
10	Correct	121 ms	82508 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	49240 KB	Output is correct
2	Correct	21 ms	49244 KB	Output is correct
3	Correct	21 ms	49500 KB	Output is correct
4	Correct	123 ms	82512 KB	Output is correct
5	Correct	117 ms	82512 KB	Output is correct
6	Correct	113 ms	82516 KB	Output is correct
7	Correct	118 ms	82492 KB	Output is correct
8	Correct	119 ms	82564 KB	Output is correct
9	Correct	113 ms	82448 KB	Output is correct
10	Correct	121 ms	82508 KB	Output is correct
11	Correct	29 ms	50372 KB	Output is correct
12	Correct	126 ms	82488 KB	Output is correct
13	Correct	124 ms	82540 KB	Output is correct
14	Correct	112 ms	82560 KB	Output is correct
15	Correct	144 ms	82444 KB	Output is correct
16	Correct	113 ms	82640 KB	Output is correct
17	Correct	121 ms	82560 KB	Output is correct
18	Correct	119 ms	82560 KB	Output is correct
19	Correct	111 ms	82396 KB	Output is correct
20	Correct	128 ms	82516 KB	Output is correct