Submission #703711

#	Time	Username	Problem	Language	Result	Execution time	Memory
703711		600Mihnea	Beads and wires (APIO14_beads)	C++17	100 / 100	361 ms	42704 KiB

beads

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long

void maxup(int& a, int b)
{
	a = max(a, b);
}

const int N = 200000 + 7;
const int INF = (int)1e18 + 7;
int n;
int par[N];
int parval[N];
vector<pair<int, int>> ginit[N];
vector<int> g[N];
int dp[N][2][2]; // dp[a][taken up][has bb]

void build(int a, int p = 0)
{
	vector<int> kids;
	for (auto& it : ginit[a])
	{
		int b = it.first, c = it.second;
		if (b == p)
		{
			continue;
		}
		build(b, a);
		par[b] = a;
		parval[b] = c;
		kids.push_back(b);
	}
	g[a] = kids;
}

int get(int a, bool okup, bool okhas)
{
	int sol = 0;
	maxup(sol, dp[a][0][0]);
	if (okup) maxup(sol, dp[a][1][0]);
	if (okhas) maxup(sol, dp[a][0][1]);
	if (okup && okhas) maxup(sol, dp[a][1][1]);
	return sol;
}

int best[5][5][5]; // how many legs and how many downs and how many downs from legs
int newbest[5][5][5]; // how many legs and how many downs and how many downs from legs

void clr()
{
	for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++)for (int k = 0; k < 2; k++) best[i][j][k] = newbest[i][j][k] = -INF;
	best[0][0][0] = 0;
}

void swp()
{
	for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) best[i][j][k] = newbest[i][j][k], newbest[i][j][k] = -INF;
}

void solve(int a)
{
	for (auto& b : g[a])
	{
		solve(b);
	}
	clr();
	for (auto& b : g[a])
	{
		for (int leg = 0; leg < 3; leg++)
		{
			for (int dw = 0; dw < 2; dw++)
			{
				for (int dwl = 0; dwl < 2; dwl++)
				{
					for (int l2 = 0; l2 <= 1; l2++)
					{
						for (int d2 = 0; d2 <= 1; d2++)
						{
							int val = best[leg][dw][dwl] + get(b, !l2, d2) + l2 * parval[b];
							//if (leg == 0 && dw == 0 && dwl == 0 && l2 == 1 && d2 == 0 && val == 50)
							//{
							//	cout << best[leg][dw][dwl] << "\n";
							//	cout << " : " << val << "\n";
							//	cout << leg + l2 << " " << dw + d2 * (l2 == 0) << " " << dwl + d2 * (l2 == 1) << "\n";

							//	exit(0);
							//}
							//if (leg + l2 == 0 && dw + d2 * (l2 == 0) == 0 && dwl + d2 * (l2 == 1) == 0 && val == 10)
							//{
							//	cout << leg << " " << dw << " " << dwl << "\n";
							//	cout << best[leg][dw][dwl] << "\n";
							//	cout << get(b, !l2, d2) << "\n";
							//	cout << l2 * parval[b] << "\n";
							//	cout << "aici!\n";
							//	exit(0);
							//}
							maxup(newbest[leg + l2][dw + d2 * (l2 == 0)][dwl + d2 * (l2 == 1)], val);
						}
					}
				}
			}
		}
		swp();
	}
	{
		// nu am nimic
		maxup(dp[a][0][0], best[0][0][0]);
		maxup(dp[a][0][1], best[0][1][0]);
	}
	{
		// am doua picioare
		maxup(dp[a][0][1], best[2][0][0]);
		maxup(dp[a][0][1], best[2][0][1]);
	}
	if (par[a])
	{
		// am un picior
		maxup(dp[a][1][0], best[1][0][0] + parval[a]);
		maxup(dp[a][1][1], best[1][0][1] + parval[a]);
	}
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		ginit[a].push_back({ b, c });
		ginit[b].push_back({ a, c });
	}
	build(1);
	solve(1);
	cout << get(1, 1, 1) << "\n";
	return 0;
}

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