Submission #103675

#TimeUsernameProblemLanguageResultExecution timeMemory
103675tugushkaMecho (IOI09_mecho)C++14
57 / 100
315 ms66560 KiB
#include<bits/stdc++.h> #define mp make_pair #define pb push_back using namespace std; using pii = pair < int, int >; const int N = 805; const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; char a[N][N]; pii mecho, home; int n, s, hive[N][N]; bool used[N][N]; void hive_bfs(){ memset( hive, 11, sizeof(hive) ); queue < pii > q; for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++){ if( a[i][j] == 'H' ){ q.push( mp( i, j ) ); hive[i][j] = 0; } } int dis = 0; while( !q.empty() ){ dis += s; int sz = q.size(); while( sz-- ){ int x, y; tie(x, y) = q.front(); q.pop(); for(int i = 0 ; i < 4 ; i++){ int tx = x+dx[i], ty = y+dy[i]; if( tx < 0 || ty < 0 || tx >= n || ty >= n ) continue; if( a[tx][ty] == 'G' && hive[tx][ty] > 2e6 ){ hive[tx][ty] = dis; q.push( mp( tx, ty ) ); } } } } /* for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < n ; j++){ if( hive[i][j] > 2e6 ) printf("@@ "); else printf("%2d ", hive[i][j]); } printf("\n"); } */ } bool mecho_bfs(int start_time){ memset( used, 0, sizeof(used) ); queue < pii > q; q.push( mecho ); int dis = start_time; while( !q.empty() ){ dis++; // cout << "dis " << dis << " : "; int sz = q.size(); while( sz-- ){ int x, y; tie(x, y) = q.front(); q.pop(); for(int i = 0 ; i < 4 ; i++){ int tx = x+dx[i], ty = y+dy[i]; if( tx < 0 || ty < 0 || tx >= n || ty >= n ) continue; if( !used[tx][ty] && a[tx][ty] == 'G' && hive[tx][ty] > dis ){ used[tx][ty] = 1; // cout << "( " << tx << ',' << ty << " ), "; q.push( mp( tx, ty ) ); } } } // cout << endl; } return used[ home.first ][ home.second ]; } int main(){ scanf("%d %d", &n, &s); for(int i = 0 ; i < n ; i++){ scanf("%s", a[i]); } hive_bfs(); for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < n ; j++){ if( a[i][j] == 'D' ){ home = mp( i, j ); a[i][j] = 'G'; } if( a[i][j] == 'M' ){ mecho = mp( i, j ); } } if( !mecho_bfs( 0 ) ){ printf("-1\n"); return 0; } int l = 0, r = n*n, res; while( l <= r ){ int mid = (l+r)/2; if( mecho_bfs( s*(mid) ) ){ res = mid; l = mid+1; } else { r = mid-1; } } /* int res = 0; while( mecho_bfs( s*(res+1) ) ) res++; */ cout << res << endl; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &s);
  ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
   ~~~~~^~~~~~~~~~~~
mecho.cpp:124:10: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << res << endl;
          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...