Submission #790953

#TimeUsernameProblemLanguageResultExecution timeMemory
790953GrayMecho (IOI09_mecho)C++17
38 / 100
265 ms11804 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> #define ll long long #define ld long double #define ln "\n" #define ff first #define ss second #define INF 2e9 using namespace std; void solve(){ ll n, s; cin >> n >> s; vector<vector<char>> gr(n, vector<char>(n)); vector<pair<ll, ll>> hvs; pair<ll, ll> bcor, hcor; for (ll i=0; i<n; i++){ for (ll j=0; j<n; j++){ cin >> gr[i][j]; if (gr[i][j]=='H'){ hvs.push_back({i, j}); }else if (gr[i][j]=='M'){ bcor = {i, j}; }else if (gr[i][j]=='D'){ hcor = {i, j}; } } } vector<vector<ll>> hpath(n, vector<ll>(n, INF)); //Generate HPATH in O(N^2) queue<pair<ll, ll>> q; for (auto hive:hvs){ hpath[hive.ff][hive.ss]=1; q.push({hive.ff, hive.ss}); } while (!q.empty()){ pair<ll, ll> hive = q.front(); q.pop(); long long xsh, ysh; xsh=1; ysh=0; if ((hive.ff+xsh<n and hive.ff+xsh>=0) and hpath[hive.ff+xsh][hive.ss+ysh]==INF and (hive.ss+ysh<n and hive.ss+ysh>=0) and (gr[hive.ff+xsh][hive.ss+ysh]=='G' or gr[hive.ff+xsh][hive.ss+ysh]=='M')){ q.push({hive.ff+xsh, hive.ss+ysh}); hpath[hive.ff+xsh][hive.ss+ysh]=hpath[hive.ff][hive.ss]+1; } xsh=-1, ysh=0; if ((hive.ff+xsh<n and hive.ff+xsh>=0) and hpath[hive.ff+xsh][hive.ss+ysh]==INF and (hive.ss+ysh<n and hive.ss+ysh>=0) and (gr[hive.ff+xsh][hive.ss+ysh]=='G' or gr[hive.ff+xsh][hive.ss+ysh]=='M')){ q.push({hive.ff+xsh, hive.ss+ysh}); hpath[hive.ff+xsh][hive.ss+ysh]=hpath[hive.ff][hive.ss]+1; } xsh=0; ysh=1; if ((hive.ff+xsh<n and hive.ff+xsh>=0) and hpath[hive.ff+xsh][hive.ss+ysh]==INF and (hive.ss+ysh<n and hive.ss+ysh>=0) and (gr[hive.ff+xsh][hive.ss+ysh]=='G' or gr[hive.ff+xsh][hive.ss+ysh]=='M')){ q.push({hive.ff+xsh, hive.ss+ysh}); hpath[hive.ff+xsh][hive.ss+ysh]=hpath[hive.ff][hive.ss]+1; } xsh=0; ysh=-1; if ((hive.ff+xsh<n and hive.ff+xsh>=0) and hpath[hive.ff+xsh][hive.ss+ysh]==INF and (hive.ss+ysh<n and hive.ss+ysh>=0) and (gr[hive.ff+xsh][hive.ss+ysh]=='G' or gr[hive.ff+xsh][hive.ss+ysh]=='M')){ q.push({hive.ff+xsh, hive.ss+ysh}); hpath[hive.ff+xsh][hive.ss+ysh]=hpath[hive.ff][hive.ss]+1; } } auto bfs2 = [&](ll wt) -> bool{ pair<ll, ll> cord = bcor; if (hpath[cord.ff][cord.ss]-1<wt) { // cout << "Fail at start: " << hpath[cord.ff][cord.ss] << " <: " << cord.ff << "," << cord.ss << " -> " << wt << ln; return 0; } vector<vector<ll>> vi(n, vector<ll>(n, INF)); queue<pair<ll, ll>> q; q.push(cord); vi[cord.ff][cord.ss]=wt; while (!q.empty()){ pair<ll, ll> cur = q.front(); q.pop(); // cout << "(" << cur.ss << "," << cur.ff << ") -> hpath=" << hpath[cur.ff][cur.ss] << "; mdist=" << vi[cur.ff][cur.ss]-wt << "; enters at=" << (ceil((ld)(vi[cur.ff][cur.ss]-wt)/(ld)s)+wt) << "; " << " bee comes in=" << hpath[cur.ff][cur.ss] << ln; if (cur.ff>0 and vi[cur.ff-1][cur.ss]==INF and gr[cur.ff-1][cur.ss]!='T' and gr[cur.ff-1][cur.ss]!='H' and (ceil((ld)(vi[cur.ff][cur.ss]-wt+1)/(ld)s)+wt)<(hpath[cur.ff-1][cur.ss])){ // cout << (hpath[cur.ff-1][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to U: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln; vi[cur.ff-1][cur.ss]=vi[cur.ff][cur.ss]+1; q.push({cur.ff-1, cur.ss}); } if (cur.ss>0 and vi[cur.ff][cur.ss-1]==INF and gr[cur.ff][cur.ss-1]!='T' and gr[cur.ff][cur.ss-1]!='H' and (ceil((ld)(vi[cur.ff][cur.ss]-wt+1)/(ld)s)+wt)<(hpath[cur.ff][cur.ss-1])){ // cout << (hpath[cur.ff][cur.ss-1]-(vi[cur.ff][cur.ss]-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to L: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln; vi[cur.ff][cur.ss-1]=vi[cur.ff][cur.ss]+1; q.push({cur.ff, cur.ss-1}); } if (cur.ff+1<n and vi[cur.ff+1][cur.ss]==INF and gr[cur.ff+1][cur.ss]!='T' and gr[cur.ff+1][cur.ss]!='H' and (ceil((ld)(vi[cur.ff][cur.ss]-wt+1)/(ld)s)+wt)<(hpath[cur.ff+1][cur.ss])){ // cout << (hpath[cur.ff+1][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to D: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln; vi[cur.ff+1][cur.ss]=vi[cur.ff][cur.ss]+1; q.push({cur.ff+1, cur.ss}); } if (cur.ss+1<n and vi[cur.ff][cur.ss+1]==INF and gr[cur.ff][cur.ss+1]!='T' and gr[cur.ff][cur.ss+1]!='H' and (ceil((ld)(vi[cur.ff][cur.ss]-wt+1)/(ld)s)+wt)<(hpath[cur.ff][cur.ss+1])){ // cout << (hpath[cur.ff][cur.ss+1]-(vi[cur.ff][cur.ss]+1-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to R: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln; vi[cur.ff][cur.ss+1]=vi[cur.ff][cur.ss]+1; q.push({cur.ff, cur.ss+1}); } } if (vi[hcor.ff][hcor.ss]<INF) return 1; else return 0; }; ll l=-1, r=n*n+1; while (l+1<r){ ll mid = (l+r)/2; if (bfs2(mid)) { l=mid; // cout << mid << " with T" << ln; } else { r=mid; // cout << mid << " with F" << ln; } } cout << l << ln; } int main() { ll t=1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...