Submission #697832

#	Time	Username	Problem	Language	Result	Execution time	Memory
697832		vjudge1	Beads and wires (APIO14_beads)	C++14	100 / 100	109 ms	15476 KiB

beads

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=2e9;
int n,u,v,w,h[N],tot,f[N][2],g[N][2],ans,F0,F1,a[N],b[N],c[N];
struct edge {int to,val,nxt;}e[N<<1];
void add(int u,int v,int w)
{
	e[++tot]={v,w,h[u]};
	h[u]=tot;
}
void dfs1(int u,int fa)
{
	f[u][1]=-INF;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to,w=e[i].val;
		if(v==fa) continue;
		c[v]=w;dfs1(v,u);
		a[v]=max(f[v][0],f[v][1]+w);
		b[v]=w+f[v][0]-a[v];
		f[u][1]=max(f[u][1],b[v]);
		f[u][0]+=a[v];
	}
	f[u][1]+=f[u][0];
}
int F(int a,int b,int w) {return w+a-max(a,b+w);}
void dfs2(int u,int fa)
{
	int mx=-INF,sec=-INF;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		if(b[v]>mx) sec=mx,mx=b[v];
		else sec=max(sec,b[v]);
	}
	int val=F(g[u][0],g[u][1],c[u]),sum=max(g[u][0],g[u][1]+c[u]);
	ans=max(ans,f[u][0]+sum);
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		g[v][0]=f[u][0]-a[v]+sum,g[v][1]=g[v][0];
		if(b[v]==mx) g[v][1]+=max(sec,val);
		else g[v][1]+=max(mx,val);
		dfs2(v,u);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	dfs1(1,0);c[1]=-INF;dfs2(1,0);
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
beads.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43