Submission #100781

#TimeUsernameProblemLanguageResultExecution timeMemory
100781Alexa2001Mecho (IOI09_mecho)C++17
100 / 100
239 ms7032 KiB
#include <bits/stdc++.h> using namespace std; const int Nmax = 808, inf = Nmax * Nmax; int n, S; char a[Nmax][Nmax]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; int tmp[Nmax][Nmax], D[Nmax][Nmax]; queue< pair<int,int> > q; void prec() { int i, j, x, y, X, Y; for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) tmp[i][j] = inf; for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) if(a[i][j] == 'H') { q.push({i, j}); tmp[i][j] = 0; } while(q.size()) { tie(x, y) = q.front(); q.pop(); for(i=0; i<4; ++i) { X = x + dx[i]; Y = y + dy[i]; if((a[X][Y] == 'G' || a[X][Y] == 'M') && tmp[X][Y] == inf) { tmp[X][Y] = tmp[x][y] + 1; q.push({X, Y}); } } } } bool check(int T) { while(q.size()) q.pop(); int i, j, x, y, X, Y; for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) { if(a[i][j] == 'M') x = i, y = j; D[i][j] = inf; } if(!(T < tmp[x][y])) return 0; q.push({x, y}); D[x][y] = 0; while(q.size()) { tie(X, Y) = q.front(); q.pop(); for(i=0; i<4; ++i) { x = X + dx[i]; y = Y + dy[i]; if(a[x][y] == 'D') return 1; if(a[x][y] == 'G' && D[X][Y] + 1 < S * (tmp[x][y] - T) && D[x][y] == inf) { D[x][y] = D[X][Y] + 1; q.push({x, y}); } } } return 0; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin >> n >> S; int i; for(i=1; i<=n; ++i) cin >> (a[i] + 1); prec(); int st, dr, mid; st = 0; dr = n * n; while(st <= dr) { mid = (st + dr) / 2; if(check(mid)) st = mid + 1; else dr = mid - 1; } cout << dr << '\n'; return 0; }

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:64:22: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(!(T < tmp[x][y])) return 0;
              ~~~~~~~~^
mecho.cpp:64:22: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...