?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
83285358 |
Дорешивание: luogu_bot3 |
835F - 34 | GNU C++11 | Полное решение | 249 мс | 39616 КБ | 2020-06-10 12:15:56 | 2020-06-10 12:15:56 |
#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 head[N],nxt[N<<1],to[N<<1],w[N<<1]; int f[N],lp[N<<1]; ll val[N],mx[N],s[N<<1],g[N<<1]; void dfs1(int x){ vis[x]=1; for(int i=head[x];i;i=nxt[i]) if(to[i]!=f[x]){ 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){ for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa&&!in[to[i]]){ 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){ nxt[++tot]=head[a]; to[head[a]=tot]=b; w[tot]=c; } int main(){ scanf("%d",&n); for(int i=1,a,b,c;i<=n;++i){ scanf("%d%d%d",&a,&b,&c); link(a,b,c); link(b,a,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; }
?
?
?
?