Submission #442338

#TimeUsernameProblemLanguageResultExecution timeMemory
442338HaidaraMecho (IOI09_mecho)C++17
79 / 100
220 ms7184 KiB
/* * * * * * * * * *\ * Author: Haidara * * LANG: C++17 * * PROB: * \* * * * * * * * * */ #include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define int long long #define rep(i,x,n) for(int i=x;i<(n);i++) #define FOR(i,n) rep(i,0,n) #define per(i,x,n) for(int i=x;i>(n);i--) #define ROF(i,x) for(int i=x;i>=0;i--) #define v(i) vector< i > #define p(i,j) pair< i , j > #define pii pair<int,int> #define m(i,j) map< i , j > #define um(i,j) unordered_map< i , j > #define pq(i) priority_queue< i > #define ff first #define all(x) x.begin(),x.end() #define ss second #define pp push_back using namespace std; void SIO(string name="") { if(name!="") { freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } } const int inf=1LL<<62LL; const int mod=1e9+7; const int maxn=808; char a[maxn][maxn]; int n,jump; pii M,D; int dist[maxn][maxn],dx[] {-1,1,0,0},dy[] {0,0,1,-1}; bool valid(int x,int y) { return x>=0&&y>=0&&x<n&&y<n&&a[x][y]!='T'&&a[x][y]!='H'; } bool check(int st) { queue<p(pii,int)>q; if(st*jump>=dist[M.ff][M.ss]) return 0; q.push({M,st*jump}); bool vis[maxn][maxn]; FOR(i,maxn) FOR(j,maxn) vis[i][j]=0; vis[M.ff][M.ss]=1; while(q.size()) { pii f=q.front().ff; int curr=q.front().ss; q.pop(); if(f==D) return 1; FOR(i,4) { int x=f.ff+dx[i],y=f.ss+dy[i]; if(!valid(x,y)||dist[x][y]<=curr+1||vis[x][y]) continue; q.push({{x,y},curr+1}),vis[x][y]=1; } } return 0; } signed main() { SIO(""); cin>>n>>jump; queue<pii>q; FOR(i,n) { cin>>ws; FOR(j,n) { dist[i][j]=inf; cin>>a[i][j]; if(a[i][j]=='M') M= {i,j},a[i][j]='G'; else if(a[i][j]=='D') D= {i,j}; else if(a[i][j]=='H') q.push({i,j}),dist[i][j]=0; } } while(q.size()) { pii f=q.front(); q.pop(); FOR(i,4) { int x=f.ff+dx[i],y=f.ss+dy[i]; if(x>=0&&y>=0&&x<n&&y<n&&a[x][y]=='G'&&dist[x][y]==inf) dist[x][y]=dist[f.ff][f.ss]+jump,q.push({x,y}); } } int l=1,r=maxn*maxn*2,ans=-1; while(l<=r) { int mid=l+(r-l)/2; if(check(mid)) ans=max(ans,mid),l=mid+1; else r=mid-1; } cout<<ans; }

Compilation message (stderr)

mecho.cpp: In function 'void SIO(std::string)':
mecho.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...