oj.uz

Submission #703697

# Submission time Handle Problem Language Result Execution time Memory
703697 2023-02-28T06:46:56 Z 600Mihnea Beads and wires (APIO14_beads) C++17
0 / 100
 5 ms 9684 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -