제출 #88138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88138		KCSC	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	503 ms	99328 KiB

election_campaign

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

const int LOG = 19;
const int DIM = 200005;

int bit[DIM], anc[DIM][LOG], dp[DIM], aux[DIM], lev[DIM], fst[DIM], lst[DIM];
vector<tuple<int, int, int>> lis[DIM]; vector<int> edg[DIM];

void update(int p, int x) {
	for (; p < DIM; p += (p & -p)) {
		bit[p] += x; } }

int query(int p, int x = 0) {
	for (; p > 0; p -= (p & -p)) {
		x += bit[p]; } 
	return x; }

int lca(int x, int y) {
	if (lev[x] > lev[y]) {
		swap(x, y); }
	for (int i = LOG - 1; i >= 0; --i) {
		if (lev[y] - (1 << i) >= lev[x]) {
			y = anc[y][i]; } }
	for (int i = LOG - 1; i >= 0; --i) {		
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i]; y = anc[y][i]; } }
	return (x == y ? x : anc[x][0]); }

void dfs1(int x, int f) {
	static int nr = 0;
	fst[x] = ++nr; lev[x] = lev[f] + 1; anc[x][0] = f;
	for (int i = 1; i < LOG; ++i) {
		anc[x][i] = anc[anc[x][i - 1]][i - 1]; }
	for (int y : edg[x]) {
		if (y != f) {
			dfs1(y, x); } } 
	lst[x] = ++nr; }

void dfs2(int x, int f) {
	for (int y : edg[x]) {
		if (y != f) {
			dfs2(y, x); aux[x] += dp[y]; } }
	dp[x] = aux[x];
	for (auto &tp : lis[x]) {
		int l, r, c; tie(l, r, c) = tp;
		dp[x] = max(dp[x], query(fst[l]) + query(fst[r]) + aux[x] + c); }
	update(fst[x], aux[x] - dp[x]); update(lst[x], dp[x] - aux[x]); }	

int main(void) {
#ifdef HOME
	freopen("election.in", "r", stdin);
	freopen("election.out", "w", stdout); 
#endif
	int n; cin >> n;
	for (int i = 1; i < n; ++i) {
		int x, y; cin >> x >> y;
		edg[x].push_back(y); edg[y].push_back(x); }
	dfs1(1, 0); int m; cin >> m;
	while (m--) {
		int x, y, c; cin >> x >> y >> c;
		lis[lca(x, y)].emplace_back(x, y, c); }
	dfs2(1, 0); cout << dp[1] << "\n";
	return 0; }

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