Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
71226845 Дорешивание:
vjudge1
835F - 34 C++17 (GCC 7-32) Полное решение 202 мс 28744 КБ 2020-02-16 16:58:28 2020-02-16 16:58:28
→ Исходный код
#include <cstdio> 
#include <cstring>
#include <algorithm>
#define int long long
#define MAX (200000 + 7)
using namespace std;

int n,cnt=0,tot=0,cir[MAX],vis[MAX],head[MAX];
int ans1=0,ans2=1e18+5,res,we[MAX],f[MAX],l[MAX],l0[MAX],r[MAX],r0[MAX];

struct edge{int to,wei,nxt;} e[MAX<<1];
inline void adde(int x,int y,int w) {e[++tot]=(edge){y,w,head[x]},head[x]=tot;}
inline int fnd(int x,int fa=-1)
{
	if(vis[x]) return x;else vis[x]=-1;
	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) {res=fnd(e[i].to,x);if(res) return cir[++cnt]=x,we[cnt]=e[i].wei,vis[x]=1,res==x?0:res;}
	return 0;
}
inline void dfs(int x,int fa=-1)
{
	for(int i=head[x];i;i=e[i].nxt)
		if(vis[e[i].to]!=1&&e[i].to!=fa)
			dfs(e[i].to,x),ans1=max(ans1,f[x]+f[e[i].to]+e[i].wei),f[x]=max(f[x],f[e[i].to]+e[i].wei);
}
signed main()
{
	scanf("%lld",&n),memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f));
	for(int i=1,x,y,w;i<=n;i++) scanf("%lld%lld%lld",&x,&y,&w),adde(x,y,w),adde(y,x,w);
	fnd(1),we[0]=0;for(int i=1;i<=cnt;i++) dfs(cir[i]),we[i]+=we[i-1];
	res=l[0]=l0[0]=-1e18;
	for(int i=1;i<=cnt;i++) l0[i]=max(l0[i-1],f[cir[i]]+we[i]+res),l[i]=max(l[i-1],f[cir[i]]+we[i]),res=max(res,f[cir[i]]-we[i]);
    res = r[cnt+1] = r0[cnt+1] = -1e18;
    for (int i = cnt; i >= 1; i--)
    {//同上 
        r0[i] = max(r0[i+1], f[cir[i]] - we[i] + res);
        r[i] = max(r[i+1], f[cir[i]] + we[cnt]- we[i]);
        res = max(res, f[cir[i]] + we[i]);
    }
	for(int i=1;i<=cnt;i++) ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
	return printf("%lld\n",max(ans1,ans2)),0;
}
 						   			 		   	 						 		
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования