Submission #72790

#	Time	Username	Problem	Language	Result	Execution time	Memory
72790		shoemakerjo	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	784 ms	31696 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define maxn 100010

int dfsnum = 0;
int loc[maxn]; //store location in pre-order thing
int dep[maxn];

int N, M;
vector<vector<int>> adj(maxn);
int par[18][maxn]; //lca jump table

int a[maxn], b[maxn], c[maxn]; //query stuff
vector<vector<int>> quers(maxn); //queries stored at this node (i.e. I am the LCA)
int subsize[maxn]; //for hld thing
int head[maxn];

void dfs(int u, int p) {
	dep[u] = p == -1 ? 1 : dep[p] + 1;
	par[0][u] = p;
	subsize[u] = 1;
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
		subsize[u] += subsize[v];
	}

}

int walk(int u, int k) {
	for (int i = 17; i >= 0; i--) {
		if (k & (1 << i)) {
			u = par[i][u];
		}
	}
	return u;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) return lca(v, u);
	u = walk(u, dep[u]-dep[v]);
	if (u == v) return u;
	for (int i = 17; i >= 0; i--) {
		if (par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][u];
}

void dfs2(int u, int p, int h) {
	head[u] = h;
	loc[u] = ++dfsnum;
	for (int v : adj[u]) {
		if (v == p) continue;
		if (subsize[v] > (subsize[u]-1)/2) {
			dfs2(v, u, h);
		}
	}
	for (int v : adj[u]) {
		if (v == p) continue;
		if (subsize[v] > (subsize[u]-1)/2) continue;
		dfs2(v, u, v); //new head thing
	}
}

int seg[2][maxn*4];

int qu(int qs, int qe, int ss, int se, int si, int indo) {
	if (qs > qe || ss > se || qs > se || qe < ss) return 0;
	if (qs <= ss && se <= qe) return seg[indo][si];
	int mid = (ss + se)/2;
	return qu(qs, qe, ss, mid, si*2+1, indo) + 
		qu(qs, qe, mid+1, se, si*2+2, indo);
}

int query(int ss, int se, int indo) {
	return qu(ss, se, 1, N, 0, indo);
}

void up(int spot, int val, int ss, int se, int si, int indo) {
	if (ss == se) {
		seg[indo][si] += val;
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) {
		up(spot, val, ss, mid, si*2+1, indo);
	}
	else up(spot, val, mid+1, se, si*2+2, indo);
	seg[indo][si] = seg[indo][si*2+1] + seg[indo][si*2+2];
}

void update(int spot, int val, int indo) {
	up(spot, val, 1, N, 0, indo);
}

int dp[maxn];
int chsum[maxn]; //sum of dp for my children

int queryup(int lo, int hi, int indo) {

	int res = 0;
	while (lo != hi) {
		int ch = head[lo];
		if (dep[ch] <= dep[hi]) {
			ch = walk(lo, dep[lo]-dep[hi]-1);
		}
		res += query(loc[ch], loc[lo], indo);
		lo = par[0][ch];
	}

	return res;

}

void dfsdp(int u, int p) {
	for (int v : adj[u]) {
		if (v == p) continue;
		dfsdp(v, u);
		chsum[u] += dp[v];
	}
	update(loc[u], chsum[u], 1);
	dp[u] = chsum[u]; //one easy way to do it
	for (int k : quers[u]) {

		int ai = a[k];
		int bi = b[k];
		int ci = c[k];

		int tmp = 0; //temporary value
		tmp += queryup(ai, u, 1);
		tmp += queryup(bi, u, 1);

		tmp -= queryup(ai, u, 0);
		tmp -= queryup(bi, u, 0);



		tmp += chsum[u];
		tmp += ci;
		dp[u] = max(dp[u], tmp);
	}

	update(loc[u], dp[u], 0);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	int x, y;
	for (int i = 0; i < N-1; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	dfs(1, -1);
	for (int i = 1; i < 18; i++) {
		for (int u = 1; u <= N; u++) {
			if (par[i-1][u] != -1) {
				par[i][u] = par[i-1][par[i-1][u]];
			}
			else par[i][u] = -1;
		}
	}
	dfs2(1, -1, 1);

	cin >> M;
	for (int i = 1; i <= M; i++) {
		cin >> a[i] >> b[i] >> c[i];
		quers[lca(a[i], b[i])].push_back(i);
	}

	dfsdp(1, -1);
	cout << dp[1] << endl;
	cout.flush();
}

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