Submission #29676

#TimeUsernameProblemLanguageResultExecution timeMemory
29676inqrDreaming (IOI13_dreaming)C++14
0 / 100
1068 ms9592 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define rt insert #define st first #define nd second #define ll long long #define DB printf("debug\n"); using namespace std; int n,m,l; vector < pair < int , int > > ed[100005]; int rn1,rn2; bool dfsv[100005]; int enuzakyol,enuzaknod; inline void dfsmax(int vn,int wn){ if(dfsv[vn])return; dfsv[vn]=1; //printf("dfsmax %d %d %d %d\n",vn,wn,rn1,rn2); if(wn>enuzakyol){ enuzakyol=wn; enuzaknod=vn; } for(int i=0;i<(int)ed[vn].size();i++){ if(dfsv[ed[vn][i].st]==0) dfsmax(ed[vn][i].st,wn+ed[vn][i].nd); } if(rn1==vn and dfsv[rn2]==0)dfsmax(rn2,wn+l); else if(rn2==vn and dfsv[rn1]==0)dfsmax(rn1,wn+l); } int enuzak(){ enuzakyol=-1,enuzaknod=-1; memset(dfsv,0,sizeof(dfsv)); if(ed[0].size())dfsmax(0,0); else dfsmax(1,0); //printf("enuzakyol=%d enuzaknod=%d\n",enuzakyol,enuzaknod); enuzakyol=-1; memset(dfsv,0,sizeof(dfsv)); dfsmax(enuzaknod,0); return enuzakyol; } int solve(int teknod){ int enuzakyolyeni=INT_MAX; //printf("teknod=%d\n",teknod); for(int i=0;i<n;i++){ if(i!=teknod){ //printf("enuzak %d %d\n",i,teknod); rn1=i;rn2=teknod; enuzakyolyeni=min(enuzakyolyeni,enuzak()); } } return enuzakyolyeni; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N,m=M,l=L; for(int i=0;i<M;i++){ ed[A[i]].pb(mp(B[i],T[i])); ed[B[i]].pb(mp(A[i],T[i])); } int teknod=-1; for(int i=0;i<N;i++){ if(ed[i].size()==0){ //printf("i=%d i.size=%d\n",i,(int)ed[i].size()); teknod=i; } } return solve(teknod); }
#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...