|

General

# Author Problem Lang Verdict Time Memory Sent Judged
83285358 Practice:
luogu_bot3
835F - 34 GNU C++11 Accepted 249 ms 39616 KB 2020-06-10 12:15:56 2020-06-10 12:15:56

→ Source
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+7;
int n,tot=1,cnt,ok; ll ans=1e18,len;
bool vis[N],in[N];
int f[N],lp[N<<1];
ll val[N],mx[N],s[N<<1],g[N<<1];
void dfs1(int x){
vis[x]=1;
if(vis[to[i]]){
val[x]=w[i]; int y=x; ok=1;
while(y!=f[to[i]]) lp[++cnt]=y,in[y]=1,y=f[y];
return ;
}
val[x]=w[i]; f[to[i]]=x; dfs1(to[i]);
if(ok) return ;
}
}
void dfs(int x,int fa){
dfs(to[i],x);
len=max(len,mx[x]+mx[to[i]]+w[i]);
mx[x]=max(mx[x],mx[to[i]]+w[i]);
}
}
inline void link(int a,int b,int c){
}
int main(){
scanf("%d",&n);
for(int i=1,a,b,c;i<=n;++i){
scanf("%d%d%d",&a,&b,&c);
} dfs1(1);
for(int i=1;i<=cnt;++i) lp[i+cnt]=lp[i];
for(int i=1;i<=2*cnt;++i) s[i]=s[i-1]+val[lp[i]];
for(int i=1;i<=cnt;++i) dfs(lp[i],0),g[i]=g[i+cnt]=mx[lp[i]];
multiset<pair<ll,int> > s1,s2;
for(int i=1;i<cnt;++i) s1.insert(make_pair(g[i]+s[i],i)),s2.insert(make_pair(g[i]-s[i],i));
for(int i=1;i<=cnt;++i){
s1.insert(make_pair(g[i+cnt-1]+s[i+cnt-1],i+cnt-1)); s2.insert(make_pair(g[i+cnt-1]-s[i+cnt-1],i+cnt-1));
ll mx=(--s1.end())->second==(--s2.end())->second?max((----s1.end())->first+(--s2.end())->first,(--s1.end())->first+(----s2.end())->first):(--s1.end())->first+(--s2.end())->first;
ans=min(ans,max(mx,len));
s1.erase(s1.find(make_pair(g[i]+s[i],i))); s2.erase(s2.find(make_pair(g[i]-s[i],i)));
}
return printf("%lld\n",ans),0;
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?