Submission #914103

#	Time	Username	Problem	Language	Result	Execution time	Memory
914103		penguin133	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	313 ms	42488 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int ft[500005], n, S[100005], E[100005], dp[100005], par[20][100005], dep[100005];

void upd(int l, int r, int v){
	r++;
	for(;l<=n;l+=(l & -l))ft[l] += v;
	for(;r <= n; r += (r & -r))ft[r] -= v;
}

int qry(int p){
	int res = 0;
	for(;p;p-=(p & -p))res += ft[p];
	return res;
}

vector <int> adj[100005];
vector <pii> stuf[100005];
int cnt = 1;
void dfs(int x, int p, int d){
	S[x] = cnt++;
	par[0][x] = p;
	for(int i = 1; i <= 19; i++)par[i][x] = par[i-1][par[i-1][x]];
	dep[x] = d;
	for(auto i : adj[x])if(i != p)dfs(i, x, d + 1);
	E[x] = cnt - 1;
}

int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] - dep[u];
	for(int i=0;i<=19;i++)if(df >> i & 1)v = par[i][v];
	if(u == v)return u;
	for(int i=19;i>=0;i--)if(par[i][u] != par[i][v])u = par[i][u], v = par[i][v];
	return par[0][u];
}

void proc(int x, int p){
	for(auto i : adj[x]){
		if(i != p){
			proc(i, x);
		}
	}
	int sm = 0;
	for(auto i : adj[x]){
		if(i != p){
			
			upd(S[x], E[x], dp[i]);
			upd(S[i], E[i], -dp[i]);
			sm += dp[i];
		}
	}
	int ans = sm;
	for(auto i : stuf[x]){
		//cout << x << ' ' << i.se.fi << ' ' << i.se.se << ' ' << qry(S[i.se.fi]) << ' ' << qry(S[i.se.se]) << '\n';
		ans = max(ans, i.fi + qry(S[i.se.fi]) + qry(S[i.se.se]) - sm);
	}
	
	//cout << x << ' ' << sm << ' ' << ans << '\n';
	dp[x] = ans;
}

void solve(){
	cin >> n;
	for(int i=1;i<n;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, -1, 1);
	int m; cin >> m;
	while(m--){
		int a, b, c; cin >> a >> b >> c;
		stuf[lca(a, b)].push_back({c, {a, b}});
	}
	proc(1, -1);
	cout << dp[1];
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

election_campaign.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      | ^~~~

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