Submission #15854

#	Time	Username	Problem	Language	Result	Execution time	Memory
15854		myungwoo	Beads and wires (APIO14_beads)	C++14	28 / 100	1068 ms	10112 KiB

beads

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

#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())

int N;
int D[MAXN], E[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] = 0;
	for (int t: arr){
		V[t] = max(D[t], E[t]);
		D[n] += V[t]; 
	}
	for (int t: arr){
		E[n] = max(E[n], D[n] - V[t] + D[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);
	}
	int ans = 0;
	for (int i=1;i<=N;i++){
		dfs(i, 0);
		ans = max(ans, D[i]);
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

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