Submission #593256

#TimeUsernameProblemLanguageResultExecution timeMemory
593256Bench0310Mecho (IOI09_mecho)C++17
100 / 100
374 ms7184 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,one; cin >> n >> one; vector<string> s(n); array<int,2> bear; array<int,2> house; vector<array<int,2>> bees; for(int i=0;i<n;i++) { cin >> s[i]; for(int j=0;j<n;j++) { if(s[i][j]=='M') bear={i,j}; if(s[i][j]=='D') house={i,j}; if(s[i][j]=='H') bees.push_back({i,j}); } } auto in=[&](int r,int c)->bool{return (0<=r&&r<n&&0<=c&&c<n);}; vector<array<int,2>> z={{1,0},{-1,0},{0,-1},{0,1}}; int ltime=-1,rtime=n*n; while(ltime<rtime-1) { int m=(ltime+rtime)/2; queue<array<int,2>> qbees,qbear; vector dbee(n,vector(n,int(-1))); auto add_bee=[&](int r,int c,int nd) { if(in(r,c)&&s[r][c]!='T'&&s[r][c]!='D'&&dbee[r][c]==-1) { qbees.push({r,c}); dbee[r][c]=nd; } }; vector dbear(n,vector(n,int(-1))); auto add_bear=[&](int r,int c,int nd) { if(in(r,c)&&s[r][c]!='T'&&dbee[r][c]==-1&&dbear[r][c]==-1) { qbear.push({r,c}); dbear[r][c]=nd; } }; for(auto [r,c]:bees) add_bee(r,c,0); add_bear(bear[0],bear[1],0); for(int i=0;!qbear.empty();i++) { while(!qbear.empty()) { auto [r,c]=qbear.front(); int d=dbear[r][c]; if(d<(i-m+1)*one) { qbear.pop(); if(dbee[r][c]!=-1) continue; for(auto [dr,dc]:z) add_bear(r+dr,c+dc,dbear[r][c]+1); } else break; } while(!qbees.empty()) { auto [r,c]=qbees.front(); int d=dbee[r][c]; if(d<=i) { qbees.pop(); for(auto [dr,dc]:z) add_bee(r+dr,c+dc,dbee[r][c]+1); } else break; } } if(dbear[house[0]][house[1]]!=-1) ltime=m; else rtime=m; } cout << ltime << "\n"; return 0; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:79:36: warning: 'house.std::array<int, 2>::_M_elems[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         if(dbear[house[0]][house[1]]!=-1) ltime=m;
      |                                    ^
mecho.cpp:13:18: warning: 'bear.std::array<int, 2>::_M_elems[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 |     array<int,2> bear;
      |                  ^~~~
mecho.cpp:79:26: warning: 'house.std::array<int, 2>::_M_elems[0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         if(dbear[house[0]][house[1]]!=-1) ltime=m;
      |                          ^
mecho.cpp:13:18: warning: 'bear.std::array<int, 2>::_M_elems[1]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 |     array<int,2> bear;
      |                  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...