When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×
 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
132075919 Practice:
PrincessFKQ
835F - 34 C++14 (GCC 6-32) Accepted 202 ms 106436 KB 2021-10-16 03:29:42 2021-10-16 03:29:42
→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,e,cnt,ans,anss,ffa,p[1000005],beg[1000005],nex[1000005],to[1000005],w[1000005],a[1000005],dp[1000005],rt[1000005],l[1000005],r[1000005],ll[1000005],rr[1000005];
void add(int x,int y,int z){
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
    w[e]=z;
}
int dfs(int x,int fa){
	if(p[x])return x;
	p[x]=1;
	for(int i=beg[x];i;i=nex[i])
		if(to[i]!=fa){
			ffa=dfs(to[i],x);
			if(ffa){
				rt[++cnt]=x;
				a[cnt]=w[i];
				p[x]=2;
				return ffa==x?0:ffa;
			}
		}
	return 0;
}
void dfss(int x,int fa){
	for(int i=beg[x];i;i=nex[i])
		if(p[to[i]]!=2&&to[i]!=fa){
			dfss(to[i],x);
			ans=max(ans,dp[x]+dp[to[i]]+w[i]);
			dp[x]=max(dp[x],dp[to[i]]+w[i]);
		}
}
signed main(){
    scanf("%lld",&n);
    int x,y,z;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z);
    dfs(1,0);
    for(int i=1;i<=cnt;i++)
        dfss(rt[i],0),a[i]+=a[i-1];
    ffa=l[0]=ll[0]=-114514114514114514;
	for(int i=1;i<=cnt;i++){
		ll[i]=max(ll[i-1],dp[rt[i]]+a[i]+ffa);
		l[i]=max(l[i-1],dp[rt[i]]+a[i]);
		ffa=max(ffa,dp[rt[i]]-a[i]);
	}
	ffa=l[cnt+1]=ll[cnt+1]=-114514114514114514;
	for(int i=cnt;i>=1;i--){
		rr[i]=max(rr[i+1],dp[rt[i]]-a[i]+ffa);
		r[i]=max(r[i+1],dp[rt[i]]+a[cnt]-a[i]);
		ffa=max(ffa,dp[rt[i]]+a[i]);
	}
	anss=114514114514114514;
	for (int i=1;i<=cnt;i++)
		anss=min(anss,max(l[i-1]+r[i],max(ll[i-1],rr[i])));
	printf("%lld\n",max(ans,anss));
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details