# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
697866 | amin | Mecho (IOI09_mecho) | C++14 | 48 ms | 10968 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>
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'&&a[xxx][yyy]=='D')
{
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});
}
}
}
}
if(jj==1)
{
l=mi;
}else
r=mi;
}
cout<<l<<endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |