Submission #970852

#TimeUsernameProblemLanguageResultExecution timeMemory
970852ThunnusMecho (IOI09_mecho)C++17
100 / 100
262 ms3080 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; #define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define sz(x) (int)(x).size() #define pii pair<int,int> #define fi first #define se second const int MAXN = 800; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, -1, 0, 1}; int n, s; vector<string> forest(MAXN); queue<array<int, 3>> hives; pii start; inline bool inside(int x, int y) {return x >= 0 && x < n && y >= 0 && y < n;} inline bool check(int time){ vector<string> t_forest = forest; queue<array<int, 3>> bees = hives; queue<array<int, 3>> frontier; vector<vb> vis(vector<vb>(n, vb(n))); int minutes = 0; while(!bees.empty()){ array<int, 3> b = bees.front(); if(b[2] == time) break; bees.pop(); for(int i = 0; i < 4; i++){ int new_x = b[0] + dx[i]; int new_y = b[1] + dy[i]; if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'M')){ bees.push({new_x, new_y, b[2] + 1}); t_forest[new_x][new_y] = 'H'; } } if(t_forest[start.fi][start.se] == 'H') return false; } frontier.push({start.fi, start.se, 0}); vis[start.fi][start.se] = true; while(!frontier.empty()){ minutes++; while(frontier.front()[2] < s * minutes && !frontier.empty()){ array<int, 3> c = frontier.front(); frontier.pop(); if(t_forest[c[0]][c[1]] == 'H') continue; for(int j = 0; j < 4; j++){ int new_x = c[0] + dx[j]; int new_y = c[1] + dy[j]; if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'D') && !vis[new_x][new_y]){ if(t_forest[new_x][new_y] == 'D'){ return true; } frontier.push({new_x, new_y, c[2] + 1}); vis[new_x][new_y] = true; } } } int size = sz(bees); while(size--){ array<int, 3> b = bees.front(); bees.pop(); for(int i = 0; i < 4; i++){ int new_x = b[0] + dx[i]; int new_y = b[1] + dy[i]; if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'M')){ bees.push({new_x, new_y, b[2] + 1}); t_forest[new_x][new_y] = 'H'; } } } } return false; } int binary_search(){ int le = 0, ri = n * n; while(le <= ri){ int mid = le + ((ri - le) >> 1); if(check(mid)){ le = mid + 1; } else{ ri = mid - 1; } } return le - 1; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> s; for(int i = 0; i < n; i++){ cin >> forest[i]; for(int j = 0; j < n; j++){ if(forest[i][j] == 'H') hives.push({i, j, 0}); else if(forest[i][j] == 'M') start = {i, j}; } } cout << binary_search(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...