Submission #947940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947940	2024-03-17T09:33:36 Z	vqpahmad	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	134 ms	74600 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()
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);
	}
}
int 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(int, int)':
election_campaign.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for (auto [u, v, c] : queries[node]){
      |            ^

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	47516 KB	Output is correct
2	Correct	21 ms	47452 KB	Output is correct
3	Incorrect	21 ms	47452 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	47448 KB	Output is correct
2	Correct	20 ms	47448 KB	Output is correct
3	Correct	22 ms	47708 KB	Output is correct
4	Correct	112 ms	74200 KB	Output is correct
5	Correct	106 ms	74172 KB	Output is correct
6	Correct	96 ms	74320 KB	Output is correct
7	Correct	106 ms	74080 KB	Output is correct
8	Correct	110 ms	74072 KB	Output is correct
9	Correct	99 ms	74324 KB	Output is correct
10	Correct	107 ms	74296 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47448 KB	Output is correct
2	Correct	20 ms	47448 KB	Output is correct
3	Correct	22 ms	47708 KB	Output is correct
4	Correct	112 ms	74200 KB	Output is correct
5	Correct	106 ms	74172 KB	Output is correct
6	Correct	96 ms	74320 KB	Output is correct
7	Correct	106 ms	74080 KB	Output is correct
8	Correct	110 ms	74072 KB	Output is correct
9	Correct	99 ms	74324 KB	Output is correct
10	Correct	107 ms	74296 KB	Output is correct
11	Correct	28 ms	48524 KB	Output is correct
12	Correct	108 ms	74580 KB	Output is correct
13	Correct	105 ms	74428 KB	Output is correct
14	Correct	126 ms	74580 KB	Output is correct
15	Correct	107 ms	74600 KB	Output is correct
16	Correct	99 ms	74580 KB	Output is correct
17	Correct	107 ms	74380 KB	Output is correct
18	Correct	133 ms	74556 KB	Output is correct
19	Correct	99 ms	74472 KB	Output is correct
20	Correct	114 ms	74424 KB	Output is correct