Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
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;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования