Submission #697299

#	Time	Username	Problem	Language	Result	Execution time	Memory
697299		vjudge1	Beads and wires (APIO14_beads)	C++14	100 / 100	162 ms	36748 KiB

beads

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
	const int SZ=1<<20;
	char gchar()
	{
	    static char buf[SZ];
	    static int i=SZ;
	    if(i==SZ)i=0,fread(buf,1,SZ,stdin);
	    return buf[i++];
	}
	void pchar(char c)
	{
	    static char buf[SZ];
	    static int i=0;
	    if(c)buf[i++]=c;
	    if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
	}
	void pstr(string s,char end='\n')
	{
		for(char c:s)pchar(c);
		pchar(end);
	}
	template<typename T>void read(T &u)
	{
	    u=0;int f=1;
	    static char c;
	    while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
	    u=c-'0';
	    while((c=gchar())>='0'&&c<='9')
			u=(u<<1)+(u<<3)+(c^48);
		u*=f;
	}
	template<typename T,typename ...Args>void read(T &u,Args&...args){read(u),read(args...);}
	template<typename T>void i_write(T u)
	{
	    if(u>9)i_write(u/10);
	    pchar(u%10+'0');
	}
	template<typename T>void write(T u,char end='\n')
	{
	    if(u<0)pchar('-'),u=-u;
	    if(u>9)i_write(u/10);
	    pchar(u%10+'0');
	    pchar(end);
	}
}
using IO::read;
using IO::write;
const int N=2e5+10;
const ll inf=1e18;
int n;
vector<pii>e[N];
int v1[N],v2[N];
ll mx1[N],mx2[N],vg[N],f[N][2],g[N][2],h[N][2];
void dfs1(int u,int fa)
{
	mx1[u]=mx2[u]=-inf,v1[u]=v2[u]=0;
	for(auto it:e[u])
	{
		int v=it.fi,w=it.se;
		if(v==fa)continue;
		vg[v]=w,dfs1(v,u),f[u][0]+=max(f[v][0],f[v][1]+w);
		ll val=f[v][0]+w-max(f[v][0],f[v][1]+w);
		if(mx1[u]<val)v2[u]=v1[u],mx2[u]=mx1[u],v1[u]=v,mx1[u]=val;
		else if(mx2[u]<val)v2[u]=v,mx2[u]=val;
	}
	f[u][1]=f[u][0]+mx1[u];
}
void dfs2(int u,int fa)
{
	for(auto it:e[u])
	{
		int v=it.fi,w=it.se;
		if(v==fa)continue;
		if(v1[u]==v)swap(mx1[u],mx2[u]),swap(v1[u],v2[u]);
		h[u][0]=g[u][0]-max(f[v][0],f[v][1]+w),h[u][1]=h[u][0]+mx1[u];
		if(u>1)h[u][1]=max(h[u][1],h[u][0]+h[fa][0]+vg[u]-max(h[fa][0],h[fa][1]+vg[u]));
		g[v][0]=f[v][0]+max(h[u][0],h[u][1]+w);
		if(mx1[u]<mx2[u])swap(mx1[u],mx2[u]),swap(v1[u],v2[u]);
		dfs2(v,u);
	}
}
int main()
{
	read(n);
	for(int i=1,x,y,z;i<n;i++)
		read(x,y,z),e[x].push_back({y,z}),e[y].push_back({x,z});
	dfs1(1,0),g[1][0]=f[1][0],dfs2(1,0);
	ll ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,g[i][0]);
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'char IO::gchar()':
beads.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |      if(i==SZ)i=0,fread(buf,1,SZ,stdin);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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