Submission #39758

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

beads

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

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

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

	if (!check[x][y]) {
		check[x][y] = true;
		if (y) {
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					long long 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) {
					long long Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					long long 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,(long long)z }), r[y].push_back({ x,(long long)z });
	}
	printf("%lld", 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