Submission #15851

#	Time	Username	Problem	Language	Result	Execution time	Memory
15851		myungwoo	Beads and wires (APIO14_beads)	C++14	0 / 100	16 ms	9728 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

int N;
int D[MAXN], E[MAXN], up[MAXN], V[MAXN];
vector <int> con[MAXN], conv[MAXN];

void dfs(int n, int from)
{
	vector <int> arr;
	for (int i=sz(con[n]);i--;){
		int t = con[n][i], v = conv[n][i];
		if (t == from) continue;
		up[t] = v; dfs(t, n);
		V[t] = D[t] - max(D[t], E[t]) + up[t];
		arr.pb(t);
	}
	sort(all(arr), [](const int &a, const int &b){
		return V[a] > V[b];
	});
	D[n] = E[n] = 0;
	if (arr.empty()) return;
	for (int t: arr) D[n] += max(D[t], E[t]);
	E[n] = D[n];
	if (sz(arr) > 1)
		D[n] += max(0, V[arr[0]] + V[arr[1]]);
	E[n] += up[n] + V[arr[0]];
}

int main()
{
	scanf("%d", &N);
	for (int i=1;i<N;i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		con[a].pb(b); conv[a].pb(c);
		con[b].pb(a); conv[b].pb(c);
	}
	dfs(1, 0);
	printf("%d\n", D[1]);
}

Compilation message (stderr)

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

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