Submission #625274

#	Time	Username	Problem	Language	Result	Execution time	Memory
625274		GusterGoose27	Beads and wires (APIO14_beads)	C++11	0 / 100	4 ms	5032 KiB

beads

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5;
int n;
int dp[MAXN][2]; // open, closed
vector<pii> edges[MAXN];
int par_val[MAXN];

struct comp {
	bool operator()(int &a, int &b) {
		return a > b;
	}
} comp;

void dfs(int cur = 0, int p = -1) {
	int o_sum = 0;
	vector<int> diffs;
	for (pii edge: edges[cur]) {
		int next = edge.first;
		if (next == p) continue;
		par_val[next] = edge.second;
		dfs(next, cur);
		o_sum += dp[next][0];
		diffs.push_back(edge.second+dp[next][1]-dp[next][0]);
	}
	sort(diffs.begin(), diffs.end(), comp);
	int ex = 0;
	if (diffs.size() >= 2) ex = diffs[0]+diffs[1];
	dp[cur][1] = max(ex, 0)+o_sum;
	if (diffs.size() == 1 || (diffs.size() >= 2 && par_val[cur] > diffs[1])) ex = diffs[0]+par_val[cur];
	dp[cur][0] = max(ex, 0)+o_sum;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y, w;
		cin >> x >> y >> w; x--; y--;
		edges[x].push_back(pii(y, w));
		edges[y].push_back(pii(x, w));
	}
	dfs();
	cout << dp[0][1] << "\n";
}

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