Submission #26098

#	Time	Username	Problem	Language	Result	Execution time	Memory
26098		nibnalin	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	5120 KiB

beads

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(2e5)+5, inf = int(1e9)+5;

int dp[maxn][2], dpmx[maxn], dp2[maxn];
vector<pair<int, int>> graph[maxn];

void dfs(int node, int par)
{
	pair<int, int> opt = {-inf, -inf};
	for(auto it: graph[node])
	{
		if(it.first != par)
		{
			dfs(it.first, node);
			dpmx[it.first] = max(dp[it.first][0], dp[it.first][1]+it.second);
			dp2[node] += dpmx[it.first];
			int tmp = it.second+dp[it.first][0]-dpmx[it.first];
			if(tmp > opt.first)
			{
				opt.second = opt.first;
				opt.first = tmp;
			}
			else if(tmp > opt.second)
			{
				opt.second = tmp;
			}
		}
	}

	dp[node][0] = dp2[node]+max(0, opt.first+opt.second);
	dp[node][1] = dp2[node]+opt.first;
}

int main(void)
{
	int n, u, v, c;
	scanf("%d", &n);
	for(int i = 1;i < n;i++)
	{
		scanf("%d%d%d", &u, &v, &c);
		u--, v--;
		graph[u].push_back({v, c});
		graph[v].push_back({u, c});
	}

	dfs(0, -1);
	printf("%d\n", dp[0][0]);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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