Submission #697689

#TimeUsernameProblemLanguageResultExecution timeMemory
697689aminMecho (IOI09_mecho)C++14
0 / 100
41 ms11228 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int b[4]={0,0,-1,1}; int c[4]={-1,1,0,0}; char mo[4]={'L','R','U','D'}; int main() { /* freopen("piggyback.in","r",stdin); freopen("piggyback.out","w",stdout);*/ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,m,k; cin>>n>>k; m=n; int enx,eny; char a[n][m]; ll val[n][m]; char pre[n][m]; queue<pair<int,int> >q; int x,y; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { val[i][j]=1e18; cin>>a[i][j]; if(a[i][j]=='M') { x=i; y=j; } if(a[i][j]=='D') { enx=i; eny=j; } if(a[i][j]=='H') { q.push({i,j}); val[i][j]=1; } } } while(!q.empty()) { int xx=q.front().first; int yy=q.front().second; q.pop(); for(int i=0;i<4;i++) { int xxx=xx+b[i]; int yyy=yy+c[i]; if(xxx<0||xxx>=n||yyy<0||yyy>=m) continue; if(val[xxx][yyy]==1e18&&a[xxx][yyy]!='T') { val[xxx][yyy]=val[xx][yy]+1; q.push({xxx,yyy}); } } } ll vall[n][m]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { vall[i][j]=0; } } /* for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cout<<val[i][j]<<' '; } cout<<endl; }*/ ll l=-1; ll r=1e18; ll jj=0; while((l+1)<r) { jj=0; q.push({x,y}); int ansx=-1,ansy=-1; ll mi=(l+r)/2; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { vall[x][j]=0; } } vall[x][y]=1; if(mi>=(val[x][y]-1)) { //cout<<1<<endl; r=mi; continue; } while(!q.empty()) { int xx=q.front().first; int yy=q.front().second; /* if(l==0) { cout<<xx<<' '<<yy<<endl; }*/ // cout<<xx<<' '<<yy<<endl; q.pop(); if(xx==enx&&yy==eny) { jj=1; break; } for(int i=0;i<4;i++) { int xxx=xx+b[i]; int yyy=yy+c[i]; if(xxx<0||xxx>=n||yyy<0||yyy>=m) continue; if(vall[xxx][yyy]==0&&a[xxx][yyy]!='T') { vall[xxx][yyy]=vall[xx][yy]+1; if(xxx==enx&&yyy==eny) { jj=1; break; } if((vall[xxx][yyy]-1)/k<val[xxx][yyy]-1-mi) { q.push({xxx,yyy}); } } } } for(int i=0;i<4;i++) { int xx=enx+b[i]; int yy=eny+c[i]; if(vall[xx][yy]!=0) jj=1; } if(jj) { r=mi; } else l=mi; } cout<<l<<endl; }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:98:8: warning: unused variable 'ansx' [-Wunused-variable]
   98 |    int ansx=-1,ansy=-1;
      |        ^~~~
mecho.cpp:98:16: warning: unused variable 'ansy' [-Wunused-variable]
   98 |    int ansx=-1,ansy=-1;
      |                ^~~~
mecho.cpp:25:9: warning: unused variable 'pre' [-Wunused-variable]
   25 |    char pre[n][m];
      |         ^~~
mecho.cpp:159:12: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
  159 |        int yy=eny+c[i];
      |            ^~
mecho.cpp:108:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |    if(mi>=(val[x][y]-1))
      |            ~~~~~~~~^
mecho.cpp:158:12: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  158 |        int xx=enx+b[i];
      |            ^~
mecho.cpp:108:20: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |    if(mi>=(val[x][y]-1))
      |            ~~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...