제출 #125121

#제출 시각아이디문제언어결과실행 시간메모리
125121TadijaSebez구슬과 끈 (APIO14_beads)C++11
57 / 100
41 ms6140 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int inf=1e9+7;
vector<pair<int,int>> E[N];
int dp[N][2],up[N][2];
void DFS(int u, int p, int w)
{
	dp[u][0]=0;
	int mx=-inf;
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		DFS(v,u,e.second);
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		mx=max(mx,dp[v][0]+w+e.second-max(dp[v][0],dp[v][1]));
	}
	dp[u][1]=dp[u][0]+mx;
}
int ans;
void Solve(int u, int p, int w)
{
	ans=max(ans,max(up[u][0],up[u][1])+dp[u][0]);
	int fir=-inf,sec=-inf,cnt=0;
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		int tmp=dp[v][0]-max(dp[v][0],dp[v][1])+e.second;
		if(fir<tmp) sec=fir,fir=tmp;
		else if(sec<tmp) sec=tmp;
		cnt++;
	}
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		int tmp=dp[v][0]-max(dp[v][0],dp[v][1])+e.second;
		int sum=dp[u][0]-max(dp[v][0],dp[v][1]);
		if(u!=1) up[v][1]=up[u][0]+w+e.second+sum;
		if(cnt>1)
		{
			int add=fir;
			if(fir==tmp) add=sec;
			up[v][1]=max(up[v][1],max(up[u][1],up[u][0])+e.second+add+sum);
		}
		up[v][0]=max(up[u][0],up[u][1])+sum;
		Solve(v,u,e.second);
	}
}
int main()
{
	int n,u,v,w;
	scanf("%i",&n);
	for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
	DFS(1,0,0);
	Solve(1,0,0);
    printf("%i\n",ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp: In function 'int main()':
beads.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
beads.cpp:54:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...