Submission #39756

#	Time	Username	Problem	Language	Result	Execution time	Memory
39756		14kg	Beads and wires (APIO14_beads)	C++11	0 / 100	5 ms	4992 KiB

beads

#include <stdio.h>
#include <vector>
#include <algorithm>
#define N 200001
#define INF 1000000000

using namespace std;
int n, dp[N][2];
bool check[N][2];
vector<pair<int, int> > r[N];

int max2(int x, int y) { return x > y ? x : y; }
int f(int x, int y, int up) {
	int MAX1 = -INF, MAX2 = -INF;

	if (!check[x][y]) {
		check[x][y] = true;
		if (y) {
			for (auto i : r[x])
				if (i.first != up) {
					int Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					int temp = i.second + f(i.first, 0, x) - Push;
					if (MAX1 < temp) MAX1 = temp;
					dp[x][y] += Push;
				}
			dp[x][y] += MAX1;
		}
		else {
			for (auto i : r[x])
				if (i.first != up) {
					int Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					// if (x == 1 && y == 0) printf(" >> %d %d %d\n",i.first ,Push, i.second + f(i.first, 0, x) - Push);
					int temp = i.second + f(i.first, 0, x) - Push;
					if (MAX1 < temp) MAX2 = MAX1, MAX1 = temp;
					else if (MAX2 < temp) MAX2 = temp;
					dp[x][y] += Push;
				}
			dp[x][y] += max2(0, MAX1 + MAX2);
		}
	} return dp[x][y];
}
int main() {
	int x, y, z;

	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d %d %d", &x, &y, &z);
		r[x].push_back({ y,z }), r[y].push_back({ x,z });
	}
	printf("%d", f(1, 0, 0));
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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