Submission #535828

#TimeUsernameProblemLanguageResultExecution timeMemory
535828SlavicGMecho (IOI09_mecho)C++17
100 / 100
186 ms11360 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(),v.rend() #define pb push_back #define sz(a) (int)a.size() #define int long long const int N = 805; char c[N][N]; int n, s; bool ok(int i, int j) { return (i >= 0 && j >= 0 && i < n && j < n && c[i][j] != 'T' && c[i][j] != 'H'); } vector<vector<int>> bfs(vector<pair<int,int>> nodes, char forbidden) { vector<vector<int>> dist(n, vector<int>(n, INT_MAX)); queue<pair<int,int>> q; for(auto f: nodes) { dist[f.first][f.second] = 0; q.push({f.first, f.second}); } while(!q.empty()) { int i = q.front().first, j = q.front().second; q.pop(); if(ok(i + 1, j) && c[i + 1][j] != forbidden && dist[i + 1][j] == INT_MAX) { dist[i + 1][j] = dist[i][j] + 1; q.push({i + 1, j}); } if(ok(i - 1, j) && c[i - 1][j] != forbidden && dist[i - 1][j] == INT_MAX) { dist[i - 1][j] = dist[i][j] + 1; q.push({i - 1, j}); } if(ok(i, j + 1) && c[i][j + 1] != forbidden && dist[i][j + 1] == INT_MAX) { dist[i][j + 1] = dist[i][j] + 1; q.push({i, j + 1}); } if(ok(i, j - 1) && c[i][j - 1] != forbidden && dist[i][j - 1] == INT_MAX) { dist[i][j - 1] = dist[i][j] + 1; q.push({i, j - 1}); } } return dist; } vector<vector<int>> bees; bool dfs(int startx, int starty, int val) { queue<pair<pair<int, int>, int>> q; q.push({{startx, starty}, 0}); if(val >= bees[startx][starty]) return false; vector<vector<int>> dist(n, vector<int>(n, -1)); dist[startx][starty] = val; while(!q.empty()) { int i = q.front().first.first, j = q.front().first.second, moves = q.front().second; q.pop(); if(c[i][j] == 'D') return true; if(ok(i + 1, j) && dist[i + 1][j] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i + 1][j]) { dist[i + 1][j] = dist[i][j] + ((moves + 1) % s == 0); q.push({{i + 1, j}, moves + 1}); } if(ok(i - 1, j) && dist[i - 1][j] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i - 1][j]) { dist[i - 1][j] = dist[i][j] + ((moves + 1) % s == 0); q.push({{i - 1, j}, moves + 1}); } if(ok(i, j + 1) && dist[i][j + 1] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i][j + 1]) { dist[i][j + 1] = dist[i][j] + ((moves + 1) % s == 0); q.push({{i, j + 1}, moves + 1}); } if(ok(i, j - 1) && dist[i][j - 1] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i][j - 1]) { dist[i][j - 1] = dist[i][j] + ((moves + 1) % s == 0); q.push({{i, j - 1}, moves + 1}); } } return false; } void solve() { cin >> n >> s; int startx, starty; vector<pair<int,int>> f; for(int i = 0;i < n; ++i) { for(int j = 0;j < n; ++j) { cin >> c[i][j]; if(c[i][j] == 'M') { startx = i, starty = j; } if(c[i][j] == 'H') { f.pb({i, j}); } } } bees = bfs(f, 'D'); int l = 0, r = 1e9; int ans = -1; while(l <= r) { int mid = l + r >> 1; if(dfs(startx, starty, mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << "\n"; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; //cin >> t; while(t--) { solve(); } }

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = l + r >> 1;
      |                   ~~^~~
mecho.cpp:111:15: warning: 'starty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |         if(dfs(startx, starty, mid)) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~
mecho.cpp:111:15: warning: 'startx' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...