Submission #308049

#TimeUsernameProblemLanguageResultExecution timeMemory
308049daniel920712Dreaming (IOI13_dreaming)C++14
18 / 100
1096 ms9720 KiB
#include "dreaming.h" #include <vector> #include <stdio.h> using namespace std; vector < pair < int , int > > Next[100005]; vector < int > all; bool have[100005]={0}; int a=0,b=0,c=0,t=0,big=0,bb=0,where; void F(int here,int con) { all.push_back(here); if(con>=big) { big=con; where=here; } have[here]=1; for(auto i:Next[here]) if(!have[i.first]) F(i.first,con+i.second); } void F2(int here,int Father,int con) { t=min(t,max(con,big-con)); for(auto i:Next[here]) if(i.first!=Father) F2(i.first,here,con+i.second); } void F3(int here,int Father,int con) { big=max(big,con); for(auto i:Next[here]) if(i.first!=Father) F3(i.first,here,con+i.second); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int i,how=0; for(i=0;i<M;i++) { Next[A[i]].push_back(make_pair(B[i],T[i])); Next[B[i]].push_back(make_pair(A[i],T[i])); } for(i=0;i<N;i++) { if(!have[i]) { how++; big=0; where=0; all.clear(); F(i,0); t=1e9; for(auto j:all) { big=0; F3(i,-1,0); t=min(t,big); } if(t>=a) { c=b; b=a; a=t; } else if(t>=b) { c=b; b=t; } else if(t>=c) c=t; } } if(how>=2) bb=max(bb,a+b+L); if(how>=3) bb=max(bb,b+c+2*L); return bb; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:49:22: warning: unused variable 'j' [-Wunused-variable]
   49 |             for(auto j:all)
      |                      ^
#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...