Submission #32027

#	Time	Username	Problem	Language	Result	Execution time	Memory
32027		minimario	Beads and wires (APIO14_beads)	C++14	0 / 100	8 ms	2688 KiB

beads

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

#define f first
#define s second
const int MAX = 100005;
typedef pair<int, int> pii;

vector<pii> g[MAX];
int dp[MAX][3];

int max(int a, int b, int c) { return max(max(a, b), c); }
void dfs(int u, int p=-1, int len=-1) {
	for (pii i : g[u]) {
		if (i.f == p) { continue; }
		dfs(i.f, u, i.s);
	}
	int sum = 0;
	vector<pii> unr; //unrooted
	vector<pii> edgy; // edgy
	for (pii i : g[u]) {
		if (i.f == p) { continue; }
		sum += max(dp[i.f][0], dp[i.f][1], dp[i.f][2]);
		unr.push_back({max(dp[i.f][0], dp[i.f][1], dp[i.f][2]) - i.s - dp[i.f][2], i.f});
		edgy.push_back({max(dp[i.f][0], dp[i.f][1], dp[i.f][2]) - i.s - dp[i.f][0], i.f});
	}
	sort(unr.begin(), unr.end());
	sort(edgy.begin(), edgy.end());	
	for (int i=0; i<min(2, (int)unr.size()); i++) {
		for (int j=0; j<min(2, (int)edgy.size()); j++) {
			if (unr[i].s != edgy[j].s) {
				dp[u][0] = max(dp[u][0], sum - unr[i].f - edgy[j].f);
			}
		}
	}
	if (unr.size() >= 2) {
		dp[u][0] = max(dp[u][0], unr[0].f + unr[1].f);
	}
	if (p != -1) {
		for (pii i : g[u]) {
			if (i.f == p) { continue; }
			dp[u][1] = max(dp[u][1], sum + len + i.s - max(dp[i.f][0], dp[i.f][1], dp[i.f][2]) + dp[i.f][0]);
		}
	}
	dp[u][2] = sum;
	// cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << endl;

}
int main() {
	// freopen("a.in", "r", stdin);
	// freopen("a.out", "w", stdout);
	int n; scanf("%d", &n);
	for (int i=0; i<n-1; i++) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dfs(1);
	printf("%d\n", max(dp[1][0], dp[1][1], dp[1][2]));
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
beads.cpp:54:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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