Submission #39766

#	Time	Username	Problem	Language	Result	Execution time	Memory
39766		14kg	Beads and wires (APIO14_beads)	C++11	0 / 100	6 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][4];
bool check[N][4];
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;
	long long _MAX1 = -INF, _MAX2 = -INF;
	long long __MAX1 = -INF, __MAX2 = -INF;
	int k1 = 0, k2 = 0;

	if (!check[x][y]) {
		check[x][y] = true;
		if (y == 1) {
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 3, x) + i.second, f(i.first, 2, 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;

			long long sum = 0;
			MAX1 = 0;
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 3, x) + i.second, f(i.first, 2, x));
					long long _temp = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x)) - Push;
					long long temp = i.second + f(i.first, 2, x) - Push;

					if (MAX1 < temp) MAX2 = MAX1, MAX1 = temp, k1 = i.first;
					else if (MAX2 < temp) MAX2 = temp;
					if (_MAX1 < _temp) _MAX2 = _MAX1, _MAX1 = _temp, k2 = i.first;
					else if (_MAX2 < _temp) _MAX2 = _temp;
					sum += Push;
				}
			if (k1 != k2) dp[x][y] = max2(dp[x][y], sum + MAX1 + _MAX1);
			else dp[x][y] = max2(dp[x][y], max2(sum + MAX1 + _MAX2, sum + MAX2 + _MAX2));

		}
		else if (y == 3) {
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 3, x) + i.second, f(i.first, 2, x));
					long long temp = i.second + f(i.first, 2, x) - Push;
					if (MAX1 < temp) MAX2 = MAX1, MAX1 = temp;
					else if (MAX2 < temp) MAX2 = temp;
					dp[x][y] += Push;
				}
			dp[x][y] += MAX1;
		}
		else if (y == 0) {
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 3, x) + i.second, f(i.first, 2, x));
					long long temp = i.second + f(i.first, 0, x) - Push;
					long long _temp = i.second + f(i.first, 2, x) - Push;
					long long __temp = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x)) - Push;

					if (__MAX1 < __temp) __MAX1 = __temp;

					if (MAX1 < temp) MAX2 = MAX1, MAX1 = temp, k1 = i.first;
					else if (MAX2 < temp) MAX2 = temp;
					if (_MAX1 < _temp) _MAX2 = _MAX1, _MAX1 = _temp, k2 = i.first;
					else if (_MAX2 < _temp) _MAX2 = _temp;
					dp[x][y] += Push;
				}
			if (k1 != k2) dp[x][y] = max2(dp[x][y]+max2(0,__MAX1), dp[x][y] + MAX1 + _MAX1);
			else dp[x][y] = max2(dp[x][y]+max2(0,__MAX1), max2(dp[x][y] + MAX1 + _MAX2, dp[x][y] + MAX2 + _MAX1));
		}
		else if (y == 2) {
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 3, x) + i.second, f(i.first, 2, x));

					dp[x][y] += Push;
				}
		}
	} return dp[x][y];
}
int main() {
	// freopen("input.txt", "r", stdin);
	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("> %d", f(6, 3, 1));
	printf("%lld", f(1, 0, 0));
}

Compilation message (stderr)

beads.cpp: In function 'long long int f(int, int, int)':
beads.cpp:17:27: warning: unused variable '__MAX2' [-Wunused-variable]
  long long __MAX1 = -INF, __MAX2 = -INF;
                           ^~~~~~
beads.cpp: In function 'int main()':
beads.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:96: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