Submission #113814

#	Time	Username	Problem	Language	Result	Execution time	Memory
113814		maruii	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	353 ms	31120 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

const int SIZE = 1 << 17;
struct ST {
	int V[2 * SIZE];
	void update(int s, int e, int v) {
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) V[s++] += v;
			if (~e & 1) V[e--] += v;
		}
	}
	int query(int x) {
		int ret = 0;
		for (x += SIZE; x; x >>= 1) ret += V[x];
		return ret;
	}
} seg;

int dep[100005], par[17][100005], dfn[100005], efn[100005], dfnn, A[100005], B[100005], X[100005], Y[100005];
vector<pair<int, pii> > path[100005];
vector<int> edge[100005];

void dfs0(int x, int p) {
	dep[x] = dep[p] + 1;
	dfn[x] = ++dfnn;
	par[0][x] = p;
	for (int i = 1; i < 17; ++i) par[i][x] = par[i-1][par[i-1][x]];
	for (auto i: edge[x]) {
		if (i != p) dfs0(i, x);
	}
	efn[x] = dfnn;
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 0; i < 17; ++i)
		if ((dep[x] - dep[y] >> i) & 1) x = par[i][x];
	if (x == y) return x;
	for (int i = 16; i >= 0; --i)
		if (par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
	return par[0][x];
}

void dfs(int x, int p) {
	for (auto i: edge[x]) {
		if (i == p) continue;
		dfs(i, x);
		B[x] += A[i];
	}
	A[x] = B[x];

	for (auto i: edge[x]) {
		if (i == p) continue;
		seg.update(dfn[i], efn[i], B[x] - A[i]);
	}

	for (auto i: path[x]) {
		A[x] = max(A[x], i.ff + B[i.ss.ff] + seg.query(dfn[i.ss.ff]) + B[i.ss.ss] + seg.query(dfn[i.ss.ss]) - B[x]);
	}
}


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N;
	for (int i = 1; i < N; ++i) {
		cin >> X[i] >> Y[i];
		edge[X[i]].push_back(Y[i]);
		edge[Y[i]].push_back(X[i]);
	}

	dfs0(1, 1);

	cin >> M;
	for (int i = 0; i < M; ++i) {
		int x, y, z; cin >> x >> y >> z;
		path[lca(x, y)].push_back({z, {x, y}});
	}

	dfs(1, 1);

	cout << A[1];
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int lca(int, int)':
election_campaign.cpp:41:15: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   if ((dep[x] - dep[y] >> i) & 1) x = par[i][x];
        ~~~~~~~^~~~~~~~

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