Submission #18463

#	Time	Username	Problem	Language	Result	Execution time	Memory
18463		tlwpdus	Beads and wires (APIO14_beads)	C++98	Compilation error	0 ms	0 KiB

beads

#include<stdio.h>
#include<algorithm>

#define MAXN 200010
#define MAXM 200010

using namespace std;

typedef long long ll;

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

void dfs(int here, int p, int uew) {
	int i;
	ll cnt = 0, sum0123 = 0, sum02 = 0, m0[2]={-2e9,-2e9}, m1[2]={-2e9,-2e9}, t0, t1;
	for (i=st[here];i!=-1;i=nxt[i]) {
		int there = en[i];
		if (there==p) continue;
		dfs(there,here,wei[i]);
		cnt++;
		int v = max(dyn[there][0],dyn[there][2]);
		sum0123 += max(max(dyn[there][0],dyn[there][1]),max(dyn[there][2],dyn[there][3]));
		sum02  += v;
		int val0 = dyn[there][0]-v+wei[i];
		int val1 = dyn[there][1]-v+wei[i];
		if (m0[0]<val0) m0[1]=m0[0],m0[0]=val0,t0=there;
		else if (m0[1]<val0) m0[1]=val0;
		if (m1[0]<val1) m1[1]=m1[0],m1[0]=val1,t1=there;
		else if (m1[1]<val1) m1[1]=val1;
	}
	dyn[here][0] = sum0123;
	if (cnt>1) dyn[here][1] = sum02+max(m0[0]+m0[1],(t0!=t1)?(m0[0]+m1[0]):(max(m0[1]+m1[0],m0[0]+m1[1])));
	if (cnt>0) dyn[here][2] = sum02+m0[0]+uew;
	if (cnt>0) dyn[here][3] = sum02+m1[0]+uew;
}
void process() {
	dfs(0,-1,0);
	printf("%lld\n",max(dyn[0][0],dyn[0][1]));
}

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() {
	//freopen("input.txt","r",stdin);
	input();
	process();
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:17:54: error: narrowing conversion of '-2.0e+9' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
  ll cnt = 0, sum0123 = 0, sum02 = 0, m0[2]={-2e9,-2e9}, m1[2]={-2e9,-2e9}, t0, t1;
                                                      ^
beads.cpp:17:54: error: narrowing conversion of '-2.0e+9' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
beads.cpp:17:73: error: narrowing conversion of '-2.0e+9' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
  ll cnt = 0, sum0123 = 0, sum02 = 0, m0[2]={-2e9,-2e9}, m1[2]={-2e9,-2e9}, t0, t1;
                                                                         ^
beads.cpp:17:73: error: narrowing conversion of '-2.0e+9' from 'double' to 'll {aka long long int}' inside { } [-Wnarrowing]
beads.cpp: In function 'void input()':
beads.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:60: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~