Submission #399809

#	Time	Username	Problem	Language	Result	Execution time	Memory
399809		nikatamliani	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	359 ms	48068 KiB

election_campaign

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10, LOG = 20;
vector<array<int, 3>> paths[N];
ll in[N], out[N], d[N], L[N][LOG], t[2*N][2], sum[N], dp[N];
ll n, m;
vector<int> edges[N];
void dfs(int x, int p) {
	static int timer = 0;
	in[x] = ++timer;
	L[x][0] = p;
	d[x] = d[p] + 1;
	for(int i = 1; i < LOG; ++i) {
		L[x][i] = L[L[x][i - 1]][i - 1];
	}
	for(int to : edges[x]) {
		if(to != p) {
			dfs(to, x);
		}
	}
	out[x] = ++timer;
}
bool is_anc(int x, int y) {
	return !x || in[x] <= in[y] && out[x] >= out[y];
}
int lca(int x, int y) {
	if(is_anc(x, y)) return x;
	if(is_anc(y, x)) return y;
	for(int i = LOG-1; ~i; --i) {
		if(!is_anc(L[x][i], y)) {
			x = L[x][i];
		}
	}
	return L[x][0];
}
int dist(int x, int y) {
	return abs(d[x] - d[y]);
}
int find_anc(int x, int d) {
	for(int bit = 0; bit < LOG; ++bit) {
		if(d >> bit & 1) x = L[x][bit];
	}
	return x;
}
void maxi(ll &x, ll y) {
	if(x < y) x = y;
}
void update(ll x, ll v, ll id) {
	for(; x <= 2*n; x += x & -x) {
		t[x][id] += v;
	}
}
ll query(ll x, ll id) {
	ll sum = 0;
	for(; x > 0; x -= x & -x) {
		sum += t[x][id];
	}
	return sum;
}
ll query(ll l, ll r, ll id) {
	return query(r, id) - query(l-1, id);
}
void solve(int x, int p) {
	for(int to : edges[x]) {
		if(to != p) {
			solve(to, x);
			sum[x] += dp[to];
		}
	}
	dp[x] = sum[x];
	for(auto &q : paths[x]) {
		int a = q[0];
		int b = q[1];
		int c = q[2];
		ll sum0 = query(in[x], in[a], 0);
		ll sum1 = query(in[x], in[b], 0);
		ll s = sum0 + sum1 + sum[x];
		if(a != x) {
			int pa = find_anc(a, dist(x, a) - 1);
			s -= query(in[pa], in[a], 1);
		}
		if(b != x) {
			int pb = find_anc(b, dist(x, b) - 1);
			s -= query(in[pb], in[b], 1);
		}
		maxi(dp[x], s + c);
	}
	update(in[x], sum[x], 0);
	update(out[x], -sum[x], 0);
	update(in[x], dp[x], 1);
	update(out[x], -dp[x], 1);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; ++i) {
		int u, v; cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	dfs(1, 0);
	cin >> m;
	for(int i = 0; i < m; ++i) {
		int u, v, c; cin >> u >> v >> c;
		paths[lca(u, v)].push_back({u, v, c});
	}
	solve(1, 0);
	cout << dp[1] << endl;
}

Compilation message (stderr)

election_campaign.cpp: In function 'bool is_anc(int, int)':
election_campaign.cpp:25:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |  return !x || in[x] <= in[y] && out[x] >= out[y];
      |               ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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