Submission #138452

#TimeUsernameProblemLanguageResultExecution timeMemory
138452baluteshihMecho (IOI09_mecho)C++14
100 / 100
279 ms7160 KiB
#include <bits/stdc++.h> #define pb push_back #define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ET cout << "\n" #define F first #define S second #define MP make_pair #define ALL(v) v.begin(),v.end() #define MEM memset(i,j,sizeof i) #define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;} using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int INF=1e9; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},n,s; string mp[805]; int ti[805][805],vis[805][805]; queue<pii> q; pii st; bool check(int x,int y) { return !(x<0||y<0||x>=n||y>=n||vis[x][y]||mp[x][y]=='T'); } bool check2(int x,int y) { return !(x<0||y<0||x>=n||y>=n||vis[x][y]!=INF||mp[x][y]=='T'); } int tran(int nw,int beg) { if(nw==beg) return beg; return (nw-beg-1)/s+beg+1; } bool running(int m) { queue<pii> q; for(int i=0;i<n;++i) fill(vis[i],vis[i]+n,INF); for(q.push(MP(st.F,st.S)),vis[st.F][st.S]=m;!q.empty();) { auto t=q.front(); q.pop(); if(tran(vis[t.F][t.S],m)>ti[t.F][t.S]) continue; if(tran(vis[t.F][t.S],m)==ti[t.F][t.S]&&(vis[t.F][t.S]-m)%s==0) continue; if(mp[t.F][t.S]=='D') return 1; for(int i=0;i<4;++i) if(check2(t.F+dx[i],t.S+dy[i])) q.push(MP(t.F+dx[i],t.S+dy[i])),vis[t.F+dx[i]][t.S+dy[i]]=vis[t.F][t.S]+1; } return 0; } int main() {jizz int l=-1,r; cin >> n >> s; for(int i=0;i<n;++i) cin >> mp[i]; for(int i=0;i<n;++i) for(int j=0;j<n;++j) ti[i][j]=INF; for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(mp[i][j]=='H') q.push(MP(i,j)),vis[i][j]=1,ti[i][j]=0; else if(mp[i][j]=='T'||mp[i][j]=='D') vis[i][j]=1; else if(mp[i][j]=='M') st=MP(i,j); while(!q.empty()) { auto t=q.front(); q.pop(); for(int i=0;i<4;++i) if(check(t.F+dx[i],t.S+dy[i])) q.push(MP(t.F+dx[i],t.S+dy[i])),vis[t.F+dx[i]][t.S+dy[i]]=1,ti[t.F+dx[i]][t.S+dy[i]]=ti[t.F][t.S]+1; } for(r=ti[st.F][st.S];r-l>1;) { int m=(l+r)/2; if(running(m)) l=m; else r=m; } cout << l << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...