oj.uz

Submission #7661

# Submission time Handle Problem Language Result Execution time Memory
7661 2014-08-13T11:42:43 Z myungwoo Beads and wires (APIO14_beads) C++
0 / 100
 12 ms 9728 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Incorrect 10 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Incorrect 10 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Incorrect 10 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 10 ms 9700 KB Output is correct
6 Incorrect 10 ms 9728 KB Output isn't correct
7 Halted 0 ms 0 KB -