Submission #697385

#	Time	Username	Problem	Language	Result	Execution time	Memory
697385		vjudge1	구슬과 끈 (APIO14_beads)	C++14	100 / 100	217 ms	33780 KiB

beads

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,f[201000];
ll aw[201000];
struct ed{int v;ll w;};
vector<ed>g[201000];
const ll I=1e18;
ll dp[201000][2],dp2[201000][2];
ll a1[201000],a2[201000];
int son[201000];
void dfs(int x){
	dp[x][0]=0;
	ll m1=I,m2=I+1;
	for(ed t:g[x])if(f[x]!=t.v){
		int v=t.v;ll w=t.w;aw[v]=t.w;f[v]=x,dfs(v);
		ll m=max(dp[v][1]+w,dp[v][0]);
		dp[x][0]+=m,m-=(dp[v][0]+w);
		if(m<m1)m2=m1,m1=m,son[x]=v;
		else if(m<m2)m2=m;
	}
	a1[x]=m1,a2[x]=m2,dp[x][1]=dp[x][0]-a1[x];
}
void dfs2(int x){
	for(ed t:g[x])if(t.v!=f[x]){
		int v=t.v,w=t.w;
		dp2[v][0]=dp[x][0]-max(dp[v][1]+w,dp[v][0]);
		if(x>1)dp2[v][0]+=max(dp2[x][1]+aw[x],dp2[x][0]);
		ll M=((son[x]==v)?a2[x]:a1[x]);
		if(x>1)M=min(M,max(dp2[x][1]+aw[x],dp2[x][0])-(dp2[x][0]+aw[x]));
		dp2[v][1]=dp2[v][0]-M;
		dfs2(v);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back((ed){v,w});
		g[v].push_back((ed){u,w});
	}
	dfs(1);
	dfs2(1);
	ll ans=-I;
	for(int i=1;i<=n;i++){
		ll at=dp[i][0];
		if(i>1)at+=max(dp2[i][0],dp2[i][1]+aw[i]);
		ans=max(ans,at);
	}
	return printf("%lld",ans),0;
} 

Compilation message (stderr)

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

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