Submission #7519

#TimeUsernameProblemLanguageResultExecution timeMemory
7519baneling100Dreaming (IOI13_dreaming)C++98
100 / 100
96 ms9464 KiB
#include "dreaming.h" #include <algorithm> #include <vector> #include <queue> #define INF 0x7fffffff using namespace std; typedef pair <int,int> ppair; vector <ppair> Road[100001]; vector <int> Diameter; vector <int> Depth; queue <int> Q; int Check[100001], D[100001], Path[100001][2], Ans=-1; int MAX(int X, int Y) { if(X>Y) return X; return Y; } void BFS(int S) { int Now, Dist, i, j, Max=-1, V, Min=INF; Check[S]=1; Q.push(S); Q.push(0); while(!Q.empty()) { Now=Q.front(); Q.pop(); Dist=Q.front(); Q.pop(); if(Max<Dist) { Max=Dist; V=Now; } j=Road[Now].size(); for(i=0 ; i<j ; i++) if(!Check[Road[Now][i].first]) { Check[Road[Now][i].first]=1; Q.push(Road[Now][i].first); Q.push(Dist+Road[Now][i].second); } } Check[V]=2; D[V]=0; Path[V][0]=-1; Max=-1; Q.push(V); while(!Q.empty()) { Now=Q.front(); Q.pop(); if(Max<D[Now]) { Max=D[Now]; V=Now; } j=Road[Now].size(); for(i=0 ; i<j ; i++) if(Check[Road[Now][i].first]==1) { Check[Road[Now][i].first]=2; D[Road[Now][i].first]=D[Now]+Road[Now][i].second; Path[Road[Now][i].first][0]=Now; Path[Road[Now][i].first][1]=Road[Now][i].second; Q.push(Road[Now][i].first); } } Diameter.push_back(Max); Dist=0; while(V>=0) { if(Min>MAX(Max,Dist)) Min=MAX(Max,Dist); Dist+=Path[V][1]; Max-=Path[V][1]; V=Path[V][0]; } Depth.push_back(Min); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int i, j; for(i=0 ; i<M ; i++) { Road[A[i]].push_back(make_pair(B[i],T[i])); Road[B[i]].push_back(make_pair(A[i],T[i])); } for(i=0 ; i<N ; i++) if(!Check[i]) BFS(i); j=Diameter.size(); for(i=0 ; i<j ; i++) { if(Ans<Diameter[i]) Ans=Diameter[i]; } if(j==1) return Ans; sort(Depth.begin(),Depth.end()); for(i=0 ; i<j-1 ; i++) { if(Ans<Depth[i]+Depth[j-1]+L) Ans=Depth[i]+Depth[j-1]+L; } if(j==2) return Ans; for(i=0 ; i<j-2 ; i++) if(Ans<Depth[i]+Depth[j-2]+2*L) Ans=Depth[i]+Depth[j-2]+2*L; return Ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...