Submission #1201068

#TimeUsernameProblemLanguageResultExecution timeMemory
1201068abckefjiMecho (IOI09_mecho)C++20
31 / 100
212 ms11440 KiB
// #include "myheader.h" #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include<bits/stdc++.h> using namespace std; #define ll long long #define pi pair<int, int> #define ti tuple<int, int, int> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() vector<vector<char>> grid; vector<vector<ll>> t; vector<pi> direction={{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int n; ll s; int si=-1, sj=-1, ei=-1, ej=-1; bool bfs(ll mid) { vector<vector<ll>> step(n, vector<ll>(n, -1)); queue<pi> nq; step[si][sj]=s*mid; nq.push({si, sj}); while(nq.size()) { auto [i, j]=nq.front(); nq.pop(); if(grid[i][j]=='D') return true; for(auto &[di, dj]: direction) { int ni=i+di; int nj=j+dj; if(ni>=0 && nj>=0 && ni<n && nj<n && (step[i][j]+1)<s*t[ni][nj] && grid[ni][nj]!='T' && step[ni][nj]==-1) { step[ni][nj]=step[i][j]+1; nq.push({ni, nj}); } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> s; grid.resize(n, vector<char>(n)); t.resize(n, vector<ll>(n, LLONG_MAX)); queue<pi> q; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cin >> grid[i][j]; if(grid[i][j]=='H') { q.push({i, j}); // t[i][j]=0; } else if(grid[i][j]=='M') { si=i; sj=j; } else if(grid[i][j]=='D') { ei=i; ej=j; } } } while(q.size()) { auto [i, j]=q.front(); q.pop(); for(auto &[di, dj]: direction) { int ni=i+di; int nj=j+dj; if(ni>=0 && nj>=0 && ni<n && nj<n && t[ni][nj]==LLONG_MAX && (grid[ni][nj]!='T' && grid[ni][nj]!='D')) { if(t[i][j] == LLONG_MAX) t[ni][nj] = 1; else t[ni][nj]=t[i][j]+1; q.push({ni, nj}); } } } ll l=-1, r=INT_MAX; while(l<r) { ll mid=(l+r+1)/2; if(bfs(mid)) { l=mid; } else { r=mid-1; } } cout << l; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...