Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
97164538 Дорешивание:
QQH
835F - 34 GNU C++11 Полное решение 124 мс 26340 КБ 2020-10-30 14:42:42 2020-10-30 14:42:42
→ Исходный код
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,edgenum=1,p[N],vis[N],head[N],Next[N*2],vet[N*2],val[N*2];
ll ans1,ans2=1e18,s[N],f[N],l[N],l2[N],r[N],r2[N];
void add(int u,int v,int w){
	edgenum++;
	Next[edgenum]=head[u];
	vet[edgenum]=v;
	val[edgenum]=w;
	head[u]=edgenum;
}
int dfs(int u,int fa){
	if(vis[u])return u;
	vis[u]=1;
	for(int e=head[u];e;e=Next[e]){
		int v=vet[e];
		if(v==fa)continue;
		int tmp=dfs(v,u);
		if(tmp){
			p[++m]=u;s[m]=val[e];
			vis[u]=2;
			if(tmp==u)return 0;
			else return tmp;
		}
	}
	return 0;
}
void dfs2(int u,int fa){
	for (int e=head[u];e;e=Next[e]){
		int v=vet[e];
		if(v==fa||vis[v]==2)continue;
		dfs2(v,u);
		ans1=max(ans1,f[u]+f[v]+val[e]);
		f[u]=max(f[u],f[v]+val[e]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,-1);
	for(int i=1;i<=m;i++){
		dfs2(p[i],0);
		s[i]+=s[i-1];
	}
	ll res=-1e18;
	l[0]=l2[0]=-1e18;
	for(int i=1;i<=m;i++){
		l[i]=max(l[i-1],f[p[i]]+s[i]);
		l2[i]=max(l2[i-1],f[p[i]]+s[i]+res);
		res=max(res,f[p[i]]-s[i]);
	}
	res=r[m+1]=r2[m+1]=-1e18;
	for(int i=m;i>=1;i--){
		r[i]=max(r[i+1],f[p[i]]+s[m]-s[i]);
		r2[i]=max(r2[i+1],f[p[i]]-s[i]+res);
		res=max(res,f[p[i]]+s[i]);
	}
	for(int i=1;i<=m;i++)
		ans2=min(ans2,max(l[i-1]+r[i],max(l2[i-1],r2[i])));
	printf("%lld",max(ans1,ans2));
	return 0;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования