Submission #31160

#TimeUsernameProblemLanguageResultExecution timeMemory
31160cscandkswonDreaming (IOI13_dreaming)C++14
18 / 100
69 ms10616 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; const int MAXN=100005; bool vst[MAXN], chk[MAXN]; vector< pair<int, int> > edge[MAXN]; int dep[MAXN], lng[MAXN], radious; vector<int> rad; void dfs1(int nod){ int i; vst[nod]=1, chk[nod]=1; for(i=0; i<edge[nod].size(); i++) if(!vst[edge[nod][i].first]) dfs1(edge[nod][i].first); for(i=0; i<edge[nod].size(); i++) if(!vst[edge[nod][i].first]) dep[nod]=max(dep[nod], dep[edge[nod][i].first]+edge[nod][i].second); vst[nod]=0; } void dfs2(int nod, int rt){ int i, dis, mx1=0, mx2=0, idx1; vst[nod]=1; chk[nod]=1; for(i=0; i<edge[nod].size(); i++)if(!vst[edge[nod][i].first]){ dis=dep[edge[nod][i].first]+edge[nod][i].second; if(dis>mx1) mx1=dis, idx1=i; else if(dis>mx2) mx2=dis; } lng[nod]=mx1+max(rt, mx2); if(max(mx1, rt)<radious) radious=max(mx1, rt); for(i=0; i<edge[nod].size(); i++)if(!vst[edge[nod][i].first]){ if(i==idx1) dfs2(edge[nod][i].first, max(rt, mx2)+edge[nod][i].second); else dfs2(edge[nod][i].first, max(rt, mx1)+edge[nod][i].second); } vst[nod]=0; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int i, dia=0; for(i=0; i<M; i++){ edge[A[i]].push_back(make_pair(B[i], T[i])); edge[B[i]].push_back(make_pair(A[i], T[i])); } for(i=0; i<N; i++) if(!chk[i]) dfs1(i); memset(chk, 0, sizeof chk); for(i=0; i<N; i++) if(!chk[i]){ radious=2e9; dfs2(i, 0); rad.push_back(radious); } sort(rad.begin(), rad.end(), greater<int>()); for(i=0; i<N; i++) dia=max(dia, lng[i]); if(rad.size()==1) return dia; else if(rad.size()==2) return max(dia, rad[0]+rad[1]+L); else return max(dia, max(rad[0]+rad[1]+L, rad[1]+rad[2]+L*2)); }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<edge[nod].size(); i++) if(!vst[edge[nod][i].first])
              ~^~~~~~~~~~~~~~~~~
dreaming.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<edge[nod].size(); i++) if(!vst[edge[nod][i].first])
              ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<edge[nod].size(); i++)if(!vst[edge[nod][i].first]){
              ~^~~~~~~~~~~~~~~~~
dreaming.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<edge[nod].size(); i++)if(!vst[edge[nod][i].first]){
              ~^~~~~~~~~~~~~~~~~
dreaming.cpp:35:9: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(i==idx1)
         ^~
#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...