Submission #799533

#TimeUsernameProblemLanguageResultExecution timeMemory
799533BaytoroMecho (IOI09_mecho)C++17
100 / 100
197 ms6276 KiB
#include <bits/stdc++.h> using namespace std; #define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define fr first #define sc second #define endl "\n" #define ll long long //#define int long long void fopn(string name){ freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } const ll INF=1e18,mod=1e9,N=1e7+5; int n,s; char a[805][805]; pair<int,int> cur,last; int dist[805][805][2]; vector<int> dx={1,-1,0, 0}, dy={0, 0,1,-1}; bool okh(int x, int y){ return (x>0 && x<=n && y>0 && y<=n && (a[x][y]=='M' || a[x][y]=='G' || a[x][y]=='H')); } bool okm(int x, int y){ return (x>0 && x<=n && y>0 && y<=n && (a[x][y]=='M' || a[x][y]=='G' || a[x][y]=='D')); } queue<pair<int,int>> dq; bool check(int D){ if(dist[cur.fr][cur.sc][0]<=D) return 0; while(!dq.empty()) dq.pop(); dq.push({cur.fr,cur.sc}); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) dist[i][j][1]=0; } dist[cur.fr][cur.sc][1]=1; while(!dq.empty()){ pair<int,int> a=dq.front(); dq.pop(); for(int i=0;i<4;i++){ int x=a.fr+dx[i],y=a.sc+dy[i]; int d=dist[a.fr][a.sc][1]+1; if(okm(x,y) && !dist[x][y][1]){ if((d-1)/s+1+D<=dist[x][y][0]){ dq.push({x,y}); dist[x][y][1]=d; } if(x==last.fr && y==last.sc && (d-1)/s+D-((d-1)%s==0)<=dist[x][y][0]) return 1; } } } return dist[last.fr][last.sc][1]; } void solve(){ queue<pair<int,int>> dq; 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]=='H'){ dq.push({i,j}); dist[i][j][0]=1; } else if(a[i][j]=='M') cur={i,j}; else if(a[i][j]=='D') last={i,j}; } } while(!dq.empty()){ pair<int,int> a=dq.front(); dq.pop(); for(int i=0;i<4;i++){ int x=a.fr+dx[i],y=a.sc+dy[i]; if(okh(x,y) && !dist[x][y][0]){ dist[x][y][0]=dist[a.fr][a.sc][0]+1; dq.push({x,y}); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dist[i][j][0]-=(dist[i][j][0]>0); } } dist[last.fr][last.sc][0]=1e9; int l=-1,r=1e9; while(l<r){ int md=(l)+(r-l+1)/2; if(check(md)) l=md; else r=md-1; } cout<<l<<endl; } main(){ ios; int T=1; //cin>>T; for(int i=1;i<=T;i++){ //cout<<"Case #"<<i<<": "; solve(); } }

Compilation message (stderr)

mecho.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main(){
      | ^~~~
mecho.cpp: In function 'void fopn(std::string)':
mecho.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...