Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
89840518 Дорешивание:
Jay142753869
835F - 34 GNU C++11 Полное решение 78 мс 28712 КБ 2020-08-14 07:31:33 2020-08-14 07:31:33
→ Исходный код
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005,INF=1e18+5;
struct edge {
	int to,wei,nxt;
} e[N<<1];
inline int read() {
	int x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')f^=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,tot=0,cnt=0,ans1=0,ans2=INF,res,head[N],cir[N],vis[N],f[N],we[N],l[N],l0[N],r[N],r0[N];
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() {
	n=read(),memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f));
	for(int i=1,x,y,w; i<=n; i++) x=read(),y=read(),w=read(),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]=-INF;
	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]=-INF;
	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, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования