Submission #7661

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

beads

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

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

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

void dfs(int n,int p,int u)
{
	int i;
	int sum = 0, mx1 = -2e9, mx2 = -2e9;
	for (i=sz(con[n]);i--;){
		int k = con[n][i], v = conv[n][i];
		if (k == p) continue;
		dfs(k,n,v);
		sum += max(D[k],E[k]);
		int diff = D[k]+v-max(D[k],E[k]);
		if (mx1 < diff) mx2 = mx1, mx1 = diff;
		else if (mx2 < diff) mx2 = diff;
	}
	D[n] = max(sum,mx1 > -2e9 && mx2 > -2e9 ? sum+mx1+mx2 : sum);
	E[n] = mx1 > -2e9 ? sum+mx1+u : -2e9;
}

int main()
{
	int i,j,k;
	scanf("%d",&N);
	for (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,0);
	printf("%d\n",D[1]);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:32:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k;
        ^
beads.cpp:32:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k;
          ^
beads.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
beads.cpp:36: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