Submission #124151

#	Time	Username	Problem	Language	Result	Execution time	Memory
124151		youngyojun	구슬과 끈 (APIO14_beads)	C++11	100 / 100	294 ms	33008 KiB

beads

#include <bits/stdc++.h>
#define eb emplace_back
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 200055;

ll D[MAXN*2], E[MAXN*2];
ll MX[MAXN][2];
ll S[MAXN];

int O[MAXN*2];
bitset<MAXN*2> chk;

vector<int> G[MAXN];
int cnt[MAXN];
int A[MAXN], B[MAXN], C[MAXN];

ll Ans;
int N;

int getC(int e) { return (e&1) ? N-cnt[B[e>>1]] : cnt[B[e>>1]]; }

void dfs(int i) {
	cnt[i] = 1;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		if(cnt[v]) continue;
		dfs(v);
		cnt[i] += cnt[v];
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 0; i < N-1; i++) {
		cin >> A[i] >> B[i] >> C[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}

	dfs(1);
	for(int i = 0; i < N-1; i++)
		if(cnt[A[i]] < cnt[B[i]]) swap(A[i], B[i]);
	
	fill(MX[0], MX[N]+2, -INFLL);
	
	iota(O, O+(N-1)*2, 0); sort(O, O+(N-1)*2, [&](int a, int b) {
		return getC(a) < getC(b);
	});
	for(int oi = 0, e, v, p; oi < (N-1)*2; oi++) {
		e = O[oi]; v = B[e>>1]; p = A[e>>1];
		if(e&1) swap(v, p);
		chk[e] = true;
		D[e] = S[v] - (chk[e^1] ? max(D[e^1], E[e^1]) : 0);
		if(chk[e^1]) {
			ll t = -max(D[e^1], E[e^1]) + D[e^1] + C[e>>1];
			E[e] = MX[v][0] == t ? MX[v][1] : MX[v][0];
		} else E[e] = MX[v][0];
		E[e] += D[e] + C[e>>1];

		S[p] += max(D[e], E[e]);
		{
			ll t = -max(D[e], E[e]) + D[e] + C[e>>1];
			if(MX[p][0] < t) swap(MX[p][0], t);
			if(MX[p][1] < t) swap(MX[p][1], t);
		}
	}

	for(int i = 1; i <= N; i++) {
		ll sum = 0;
		for(int e : G[i]) {
			int v = A[e]^B[e]^i;
			e = (e<<1) | (B[e] == i ? 1 : 0);
			sum += max(D[e], E[e]);
		}
		if(Ans < sum) Ans = sum;
	}

	cout << Ans << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:76:8: warning: unused variable 'v' [-Wunused-variable]
    int v = A[e]^B[e]^i;
        ^

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43