Submission #703697

#	Time	Username	Problem	Language	Result	Execution time	Memory
703697		600Mihnea	Beads and wires (APIO14_beads)	C++17	0 / 100	5 ms	9684 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;
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;
}

void solve(int a)
{
	for (auto& b : g[a])
	{
		solve(b);
	}
	{
		// don't involve him in anything
		for (auto& b : g[a])
		{
			maxup(dp[a][0][0], max({ dp[b][0][0], dp[b][1][0] }));
			maxup(dp[a][0][1], max({ dp[b][0][0], dp[b][1][0], dp[b][0][1], dp[b][1][1] }));
		}
	}
	{
		// no taken up
	
		for (auto& b : g[a])
		{
			for (auto& c : g[a])
			{
				if (b == c)
				{
					continue;
				}
				int cur = 0;
				for (auto& vert : g[a])
				{
					if (vert == b || vert == c)
					{
						cur += max({ dp[vert][0][0], dp[vert][0][1] }) + parval[vert];
					}
					else
					{
						cur += max({ dp[vert][0][0], dp[vert][1][0], dp[vert][0][1], dp[vert][1][1] });
					}
				}
				maxup(dp[a][0][1], cur);
			}
		}
	}
	if (par[a])
	{
		// taken up
		for (int h = 0; h <= 1; h++)
		{
			for (auto& b : g[a])
			{
				int cur = parval[a];
				for (auto& vert : g[a])
				{
					if (vert == b)
					{
						if (h == 0)
						{
							cur += dp[vert][0][0] + parval[vert];
						}
						else
						{
							cur += max({ dp[vert][0][0], dp[vert][0][1] }) + parval[vert];
						}
					}
					else
					{
						if (h == 0)
						{
							cur += max({ dp[vert][0][0], dp[vert][1][0] });
						}
						else
						{
							cur += max({ dp[vert][0][0], dp[vert][1][0], dp[vert][0][1], dp[vert][1][1] });
						}
					}
				}
				maxup(dp[a][1][h], cur);
			}
		}
	}
}

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);
	int sol = max({ dp[1][0][0], dp[1][0][1], dp[1][1][0], dp[1][1][1] });
	cout << sol << "\n";
	return 0;
}

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