Submission #1309642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309642		nanaseyuzuki	Election Campaign (JOI15_election_campaign)	C++20	0 / 100	100 ms	26320 KiB

election_campaign

#include <bits/stdc++.h>
// Kazusa_Megumi
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, m, d[mn], up[mn][20], st[mn], euler[mn], ft[mn], timer_dfs = 0, dp[mn][20];
vector <int> a[mn];
vector <array<int, 3>> event[mn];

int bit[mn], res = 0;

void add(int u, int val){
	while(u <= n){
		bit[u] += val;
		u += (u & -u);
	}
}

int get(int u){
	int res = 0;
	while(u){
		res += bit[u];
		u -= (u & -u);
	}
	return res;
}

void dfs(int u, int p){
	d[u] = d[p] + 1;
	st[u] = ++ timer_dfs; euler[timer_dfs] = u;
	for(auto v : a[u]){
		if(v == p) continue;
		up[v][0] = u;
		dfs(v, u);
	}
	ft[u] = timer_dfs;
}

void build(){
	for(int j = 1; j <= 16; j++){
		for(int i = 1; i <= n; i++){
			up[i][j] = up[up[i][j - 1]][j - 1];
		}
	}
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	for(int i = 16; i >= 0; i--){
		if(d[up[u][i]] >= d[v]) u = up[u][i];
	}
	if(u == v) return u;
	for(int i = 16; i >= 0; i--){
		if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
	}
	return up[u][0];
}

int jump(int u, int v){
	for(int i = 16; i >= 0; i--){
		if(d[up[u][i]] > d[v]) u = up[u][i];
	}
	return u;
}
// dp[u][0] : maximum val without going through u
// dp[u][1] : going through u
void calc(int u, int p){
	for(auto v : a[u]){
		if(v == p) continue;
		calc(v, u);
		dp[u][0] += max(dp[v][0], dp[v][1]);
	}
	int max_diff = - 1e9;
	for(auto [x, y, c] : event[u]){
		int cur = c; // difference between dp[u][0] and values when applying this project
		if(x != u){
			int p = jump(x, u);
			cur += get(st[x]) - get(st[p]) + dp[p][0] - max(dp[p][0], dp[p][1]);
		}
		if(y != u){
			int p = jump(y, u);
			cur += get(st[y]) - get(st[p]) + dp[p][0] - max(dp[p][0], dp[p][1]);
		}
		max_diff = max(max_diff, cur);
	}
	if(max_diff > -1e9){
		dp[u][1] = dp[u][0] + max_diff;
		add(st[u], dp[u][0] - dp[u][1]);
		add(ft[u] + 1, dp[u][1] - dp[u][0]);
	}
}

void solve() {
    cin >> n;
    for(int i = 1; i < n; i++){
    	int u, v; cin >> u >> v;
    	a[u].push_back(v);
    	a[v].push_back(u);	
    }
    dfs(1, 0); build();
    cin >> m;
    for(int i = 1; i <= m; i++){
    	int u, v, w; cin >> u >> v >> w;
    	event[lca(u, v)].push_back({u, v, w});
    }
    d[0] = -1;
    calc(1, 0);
    cout << max({dp[1][1], dp[1][0]}) << '\n';
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

election_campaign.cpp:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main() {
      | ^~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40