oj.uz

Submission #18461

# Submission time Handle Problem Language Result Execution time Memory
18461 2016-02-03T09:45:55 Z tlwpdus Beads and wires (APIO14_beads) C++
0 / 100
 2 ms 384 KB 
#include<stdio.h>
#include<algorithm>

#define MAXN 200010
#define MAXM 200010

using namespace std;

int n;
int nxt[MAXM*2], st[MAXN], en[MAXM*2], wei[MAXM*2];
int dyn[MAXN][2];

void dfs(int here, int p, int uew) {
	int i, cnt = 0, sum = 0, m1 = -2e9, m2 = -2e9;
	for (i=st[here];i!=-1;i=nxt[i]) {
		int there = en[i];
		if (there==p) continue;
		dfs(there,here,wei[i]);
		cnt++;
		sum += dyn[there][1];
		int val = dyn[there][0]-dyn[there][1]+wei[i];
		if (m1<val) {m2=m1;m1=val;}
		else if (m2<val) m2=val;
	}
	if (cnt<2) dyn[here][0] = sum;
	else dyn[here][0] = max(sum,sum+m1+m2);
	if (cnt<1) dyn[here][1] = dyn[here][0];
	else dyn[here][1] = max(dyn[here][0],sum+m1+uew);
}
void process() {
	dfs(0,-1,0);
	printf("%d\n",dyn[0][0]);
}

int ptr = 0;
void add_edge(int u, int v, int w) {
	nxt[ptr] = st[u];
	wei[ptr] = w;
	en[ptr] = v;
	st[u] = ptr++;
	nxt[ptr] = st[v];
	wei[ptr] = w;
	en[ptr] = u;
	st[v] = ptr++;
}
void input() {
	int i;
	scanf("%d",&n);
	for (i=0;i<n;i++) st[i] = -1;
	for (i=0;i<n-1;i++) {
		int a, b, w;
		scanf("%d %d %d",&a,&b,&w);
		add_edge(--a,--b,w);
	}
}

int main() {
	input();
	process();
	return 0;
}

Compilation message

beads.cpp: In function 'void input()':
beads.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -