?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
132075919 |
Дорешивание: PrincessFKQ |
835F - 34 | C++14 (GCC 6-32) | Полное решение | 202 мс | 106436 КБ | 2021-10-16 03:29:42 | 2021-10-16 03:29:42 |
#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; }
?
?
?
?