Submission #18461

#	Time	Username	Problem	Language	Result	Execution time	Memory
18461		tlwpdus	Beads and wires (APIO14_beads)	C++98	0 / 100	2 ms	384 KiB

beads

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43