Submission #1263117

#TimeUsernameProblemLanguageResultExecution timeMemory
1263117dhuyyyyMecho (IOI09_mecho)C++20
100 / 100
139 ms12100 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; using ll = long long; using ii = pair<int,int>; using pii = pair<int,ii>; using aa = array<int,4>; const int N = 805; const int INF = 1e9; const int MOD = 1e9+21; int n,S,c,u,v,start_x,start_y,home_x,home_y; int ans = -1,cur = -1; int Mecho[N][N],Bee[N][N]; bool vis[N][N],okay; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; char a[N][N]; queue <ii> q; bool reached(int a,int b){ return a / S < b; } bool ok(int i,int j){ return min(i,j) >= 1 && max(i,j) <= n && a[i][j] != 'H' && a[i][j] != 'T'; } bool check(int mid){ while (!q.empty()) q.pop(); q.push({start_x,start_y}); if (!reached(0,Bee[start_x][start_y] - mid)) return 0; Mecho[start_x][start_y] = 0; okay = 0; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++) vis[i][j] = 0; } vis[start_x][start_y] = 1; while (!q.empty()){ tie(u,v) = q.front(); if (u == home_x && v == home_y) return 1; q.pop(); for (int k = 0; k < 4; k++){ int x = u + dx[k]; int y = v + dy[k]; if (ok(x,y) && !vis[x][y] && reached(Mecho[u][v]+1,Bee[x][y] - mid)){ Mecho[x][y] = Mecho[u][v] + 1; vis[x][y] = 1; q.push({x,y}); } } } return 0; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> S; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ cin >> a[i][j]; if (a[i][j] == 'M'){ //Mecho pos start_x = i; start_y = j; } if (a[i][j] == 'H'){ //Hives pos q.push({i,j}); vis[i][j] = 1; } if (a[i][j] == 'D'){ //Mecho home home_x = i; home_y = j; Bee[i][j] = 1e9+5; } } } while (!q.empty()){ tie(u,v) = q.front(); q.pop(); for (int k = 0; k < 4; k++){ int x = u + dx[k]; int y = v + dy[k]; if (ok(x,y) && !vis[x][y] && a[x][y] != 'D'){ Bee[x][y] = Bee[u][v] + 1; vis[x][y] = 1; q.push({x,y}); } } } int l = 0,r = n*n,ans = -1; while(l <= r){ int mid = (l + r) >> 1; if (check(mid)){ ans = mid; l = mid + 1; } else r = mid - 1; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...