# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1119718 | sktodow | Mecho (IOI09_mecho) | C++17 | 254 ms | 8492 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
// #define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=805;
static const long long int MOD=(1LL<<61)-1;
static const long long int inf=INT64_MAX;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
void io(string name = ""){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
int n,x,mx,my;
vector<vector<char>>v(N,vector<char>(N));
vector<vector<int>>bee(N,vector<int>(N,-1));
int mec[N][N];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
bool inside(int a,int b){return ((a<=n && a>0)&&(b<=n && b>0)&&v[a][b]!='T');}
void calcbee(){
queue<array<int,3>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(v[i][j]=='H'){q.push({i,j,0});}
}
}
while(q.size()){
array<int,3>curr=q.front();
q.pop();
if(bee[curr[0]][curr[1]]!=-1){continue;}
bee[curr[0]][curr[1]]=curr[2];
for(int i=0;i<4;i++){
if(inside(curr[0]+dx[i],curr[1]+dy[i])){
q.push({curr[0]+dx[i],curr[1]+dy[i],curr[2]+1});
}
}
}
}
bool mecho(int k){
queue<array<int,3>>q;
q.push({mx,my,k});
while(q.size()){
array<int,3>curr=q.front();
q.pop();
if(mec[curr[0]][curr[1]]!=-1){continue;}
mec[curr[0]][curr[1]]=curr[2];
if(v[curr[0]][curr[1]]=='D'){return 1;}
for(int i=0;i<4;i++){
if(inside(curr[0]+dx[i],curr[1]+dy[i]) && bee[curr[0]+dx[i]][curr[1]+dy[i]]>(curr[2]+1)/x){
q.push({curr[0]+dx[i],curr[1]+dy[i],curr[2]+1});
}
}
}
return 0;
}
int32_t main(){
//io("local");
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>v[i][j];
if(v[i][j]=='M'){mx=i,my=j;}
}
}
calcbee();
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){cout<<bee[i][j]<<" ";}
// cout<<endl;
// }
int l=0,r=n*n;
bool chc=0,achc=0;
while(l<=r){
memset(mec,-1,sizeof(mec));
chc=mecho(mid*(x));
// cout<<mid<<" "<<chc<<endl;
if(chc){l=mid+1;achc=1;}
else{r=mid-1;}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){cout<<mec[i][j]<<" ";}
// cout<<endl;
// }
// cout<<endl;
}
memset(mec,-1,sizeof(mec));
if(!achc && mecho(0)){cout<<0;}
else if(!achc){cout<<-1;}
else{cout<<l-1;}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |