Submission #29630

#TimeUsernameProblemLanguageResultExecution timeMemory
29630osmanorhanDreaming (IOI13_dreaming)C++14
18 / 100
85 ms11384 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define umax( x, y ) x = max( x, y ) #define umin( x, y ) x = min( x, y ) using namespace std; const int maxn = 100000; typedef long long Lint; typedef pair<int,int> ii; typedef pair<int,ii> iii; //first - where to go //second.first - how much time to go //second.second - length of longest path starting from this edge vector<iii> w[maxn]; vector<int> v, ans; bool used[maxn]; int dfs( int n, int back ) { int ret = 0; v.pb( n ); used[n] = 1; for(int i=0;i<w[n].size();i++) if( w[n][i].fi != back ) umax( ret, w[n][i].se.se = w[n][i].se.fi + dfs( w[n][i].fi, n ) ); return ret; } bool comp( const iii &a, const iii &b ) { return a.se.se > b.se.se; } void dfs2( int n, int back, int s ) { for(int i=0;i<w[n].size();i++) if( w[n][i].fi == back ) w[n][i].se.se = s; sort( w[n].begin(), w[n].end(), comp ); for(int i=0;i<w[n].size();i++) if( w[n][i].fi != back ) { if( i ) dfs2( w[n][i].fi, n, w[n][i].se.fi+w[n][0].se.se ); else dfs2( w[n][i].fi, n, ( w[n].size()==1 ? 0:w[n][1].se.se ) + w[n][i].se.fi ); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i=0;i<M;i++) { w[ A[i] ].pb( iii( B[i], ii( T[i], 0 ) ) ); w[ B[i] ].pb( iii( A[i], ii( T[i], 0 ) ) ); } for(int i=0;i<N;i++) if( !used[i] ) { v.clear(); dfs( i, i ); dfs2( i, i, 0 ); int mini = 1e9; while( v.size() ) { int maxi = 0, n = v[v.size()-1]; for(int j=0;j<w[n].size();j++) umax( maxi, w[n][j].se.se ); umin( mini, maxi ); v.pop_back(); } ans.pb( mini ); } sort( ans.begin(), ans.end() ); reverse( ans.begin(), ans.end() ); int ret = ans[0]; if( ans.size() >= 2 ) umax( ret, ans[0]+ans[1]+L ); if( ans.size() >= 3 ) umax( ret, ans[1]+ans[2]+L+L ); return ret; }

Compilation message (stderr)

dreaming.cpp: In function 'int dfs(int, int)':
dreaming.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n].size();i++)
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n].size();i++)
                 ~^~~~~~~~~~~~
dreaming.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<w[n].size();i++)
                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<w[n].size();j++) umax( maxi, w[n][j].se.se );
                             ~^~~~~~~~~~~~
#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...