Submission #1304613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304613		hoa208	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	135 ms	39196 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
//--------------------------------------------------------------------

const ll N = 1e5 + 10;
ll n;
ll m;
vector<ll> g[N];
ll up[N][19], h[N];
ll in[N], en[N];
ll timedfs;
void dfs(ll u, ll p) {
	in[u] = ++timedfs;
	for(auto v : g[u]) {
		if(v == p) continue;
		h[v] = h[u] + 1;
		up[v][0] = u;
		FOR(i, 1, 18) up[v][i] = up[up[v][i - 1]][i - 1];
		dfs(v, u);
	}
	en[u] = timedfs;
}
ll get(ll u, ll k) {
	for(int j = 0; (1 << j) <= k; j++) {
		if(bit(k, j)) u = up[u][j];
	}
	return u;
}
ll lca(ll u, ll v) {
	if(h[u] < h[v]) swap(u, v);
	u = get(u, h[u] - h[v]);
	if(u == v) return u;
	FORD(i, 18, 0) {
		if(up[u][i] != up[v][i]) {
			u = up[u][i];
			v = up[v][i];
		}
	}
	return up[u][0];
}
struct state {
	ll u, v, c;
};
vector<state> vc[N];
ll dp[N];
const int maxbit = 1e5 + 10;
ll BIT[maxbit], BIT2[maxbit];
void update(int x, ll val, ll val2) {
	while(x <= n) {
	   BIT[x] += val;
	   BIT2[x] += val2;
	   x += x & -x; 
	}
}
ll getsum(int x) {
	ll res = 0;
	while(x > 0) {
		res += BIT[x];
		x -= x & -x;
	}
	return res;
}
ll getdp(int x) {
	ll res = 0;
	while(x > 0) {
		res += BIT2[x];
		x -= x & -x;
	}
	return res;
}
void update_lr(int l, int r, ll val, ll val2 ) {
	update(l, val, val2);
	update(r + 1, -val, -val2);
}
int walk(int x, int _n) {
	int pos = 0;
	int LG = __lg(_n);
	FORD(j, LG, 0) {
		if(pos + (1 << j) <= _n && BIT[pos + (1 << j)] < x) {
			pos += (1 << j);
			x -= BIT[pos];
		}
	}
	return pos + 1;
}
void calc(ll u, ll p) {
	ll sum_dp = 0;
	for(auto v : g[u]) {
		if(v == p) continue;
		calc(v, u);
		sum_dp += dp[v];
	}
	dp[u] = sum_dp;
	for(auto e : vc[u]) {
		ll sum = getsum(in[e.u]) + getsum(in[e.v]) + sum_dp;
		ll rem = getdp(in[e.u]) + getdp(in[e.v]);
		dp[u] = max(dp[u], sum - rem + e.c);
	}
	update_lr(in[u], en[u], sum_dp, dp[u]);
}
void hbmt() {
	cin >> n;
	FOR(i, 1, n - 1) {
		ll u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	cin >> m;
	FOR(i, 1, m) {
		ll u, v, c;
		cin >> u >> v >> c;
		ll p = lca(u, v);
		vc[p].push_back({u, v, c});
	}
	calc(1, 0);
	cout << dp[1];
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	#define NAME "hbmt"
	if(fopen(NAME".inp", "r")) {
		freopen(NAME".inp", "r", stdin);
		freopen(NAME".out", "w", stdout);
	}
	
	//int t;cin>>t;while(t--)
	hbmt();
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:137:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |                 freopen(NAME".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:138:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |                 freopen(NAME".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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