| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 17162 | erdemkiraz | 꿈 (IOI13_dreaming) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dreaming.h"
#include<algorithm>
#include<string.h>
using namespace std;
const int MV = 100010;
const int ME = MV<<1;
int st[MV], en[ME], len[ME], next[ME], nl;
void addedge(int s,int d,int l,int c)
{
next[c]=st[s];
st[s]=c;
en[c]=d;
len[c]=l;
}
int pre[MV],Q[MV],dis[MV];
bool check[MV];
int bfs1(int x)
{
int fr=1,re=0,i,ret=x;
Q[0]=x,check[x]=1,dis[x]=0;
while(fr!=re){
int t=Q[re++];
for(i=st[t];i!=-1;i=next[i]){
if(check[en[i]])continue;
int d=en[i];
check[d]=1;
dis[d]=dis[t]+len[i];
if(dis[ret]<dis[d])ret=d;
Q[fr++]=d;
}
}
for(i=0;i<fr;i++)check[Q[i]]=0;
return ret;
}
int bfs2(int x)
{
int fr=1,re=0,i,E=x;
Q[0]=x,check[x]=1;
pre[x]=-1,dis[x]=0;
while(fr!=re){
int t=Q[re++];
for(i=st[t];i!=-1;i=next[i]){
if(check[en[i]])continue;
int d=en[i];
check[d]=1;
pre[d]=t;
dis[d]=dis[t]+len[i];
if(dis[E]<dis[d])E=d;
Q[fr++]=d;
}
}
nl=max(nl,dis[E]);
int ret=dis[E],tmp=E;
while(tmp!=x){
ret=min(ret,max(dis[E]-dis[tmp],dis[tmp]));
tmp=pre[tmp];
}
return ret;
}
int AR[100010],al;
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
memset(st,-1,sizeof(st));
int i;
for(i=0;i<M;i++){
addedge(A[i],B[i],T[i],i<<1);
addedge(B[i],A[i],T[i],i<<1|1);
}
for(i=0;i<N;i++){
if(!check[i]){
AR[al++]=bfs2(bfs1(i));
}
}
sort(AR,AR+al);
if(al==1)return nl;
if(al==2)return max(nl,AR[1]+AR[0]+L);
return max(nl,max(AR[al-1]+AR[al-2]+L,AR[al-2]+AR[al-3]+L*2));
}