Submission #15853

#	Time	Username	Problem	Language	Result	Execution time	Memory
15853		myungwoo	Beads and wires (APIO14_beads)	C++14	13 / 100	10 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], F[MAXN], G[MAXN];
int 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);
		arr.pb(t);
	}
	D[n] = E[n] = F[n] = G[n] = 0;
	int def = 0;
	for (int t: arr){
		V[t] = max(max(D[t], E[t]), F[t]);
		D[n] += max(V[t], G[t]);
		def += V[t];
	}
	int mx1 = -2e9, mx2 = -2e9;
	for (int t: arr){
		if (mx1 > -2e9){
			E[n] = max(E[n], def + mx1 + E[t] - V[t] + up[t]);
			E[n] = max(E[n], def + max(mx1, mx2) + D[t] - V[t] + up[t]);
		}
		mx1 = max(mx1, -V[t]+D[t]+up[t]);
		mx2 = max(mx2, -V[t]+E[t]+up[t]);
	}
	for (int t: arr){
		F[n] = max(F[n], def - V[t] + D[t] + up[t] + up[n]);
		G[n] = max(G[n], def - V[t] + E[t] + up[t] + up[n]);
	}
}

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", max(D[1], E[1]));
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
beads.cpp:50: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: 13 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43