Submission #697690

#	Time	Username	Problem	Language	Result	Execution time	Memory
697690		amin	Mecho (IOI09_mecho)	C++14	33 / 100	49 ms	11232 KiB

mecho

#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});
            }else
            vall[xxx][yyy]=0;
           }
       }
   }
   for(int i=0;i<4;i++)
   {

       int xx=enx+b[i];
       int yy=eny+c[i];
       if(xx<0||xx>=n||yy<0||yy>=m)
            continue;

     if(vall[xx][yy]!=0)
        jj=1;
   }
   if(jj)
   {
       l=mi;
   }
    else
        r=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:161:12: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |        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:160:12: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |        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))
      |            ~~~~~~~~^

• Subtask 1: 33 / 100