|

General

# Author Problem Lang Verdict Time Memory Sent Judged
83349563 Practice:
vjudge3
835F - 34 GNU C++17 Accepted 155 ms 27304 KB 2020-06-11 08:06:57 2020-06-11 08:06:57

→ Source
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
#define N 200005
int fir[N],to[2*N],nxt[2*N],cd[2*N],cnt;
void adde(int a,int b,int c)
{
to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;cd[cnt]=c;
to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;cd[cnt]=c;
}
#define LL long long
int cir[N],fa[N],dep[N];
bool vis[N];
void findcir(int u)
{
dep[u]=dep[fa[u]]+1;
int v,p;
for(p=fir[u];p;p=nxt[p]){
v=to[p];
if(v==fa[u]) continue;
if(!dep[v]){fa[v]=u;findcir(v);}
else if(dep[v]<dep[u]){
for(int j=u;;j=fa[j]){
vis[j]=1;cir[++m]=j;
if(j==v)break;
}
}
}
}
LL hei[N],ans,D[N];
void dfs(int u,int ff)
{
int v,p,w;
for(p=fir[u];p;p=nxt[p]){
v=to[p];w=cd[p];
if(v!=ff&&!vis[v]){
dfs(v,u);
ans=max(hei[u]+hei[v]+w,ans);
hei[u]=max(hei[u],hei[v]+w);
}
}
}
LL g1[N],g2[N],h1[N],h2[N];
int main()
{
int n,i,u,v,w,p;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d%d",&u,&v,&w);
}
findcir(1);
for(i=1;i<=m;i++)dfs(cir[i],0);
cir[m+1]=cir[1];
for(i=1;i<=m;i++)
for(p=fir[cir[i]];p;p=nxt[p])
if(to[p]==cir[i+1]){D[i]=cd[p];break;}
LL sum=0,mx=hei[cir[1]]+D[1];
for(i=2;i<=m;i++){
sum+=D[i-1];
h1[i]=max(h1[i-1],hei[cir[i]]+sum);
g1[i]=max(g1[i-1],hei[cir[i]]+mx);
mx=max(mx,hei[cir[i]])+D[i];
}
sum=0;mx=hei[cir[1]]+D[m];
for(i=m;i>1;i--){
sum+=D[i];
h2[i]=max(h2[i+1],hei[cir[i]]+sum);
g2[i]=max(g2[i+1],hei[cir[i]]+mx);
mx=max(mx,hei[cir[i]])+D[i-1];
}
LL ret=1ll<<60;
for(i=1;i<=m;i++)
ret=min(ret,max(h1[i]+h2[i+1],max(g1[i],g2[i+1])));
printf("%lld",max(ans,ret));
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?