Submission #697670

#	Time	Username	Problem	Language	Result	Execution time	Memory
697670		amin	Mecho (IOI09_mecho)	C++14	28 / 100	48 ms	11228 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);
   int 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;

     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((-((vall[xxx][yyy]-1+k)/k)+val[xxx][yyy]-1)>=mi)
            {


            q.push({xxx,yyy});
            }
           }
       }
   }
       if(jj==1)
       {
           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:107:14: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |    vall[x][y]=1;
      |    ~~~~~~~~~~^~
mecho.cpp:27:8: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |    int x,y;
      |        ^
mecho.cpp:120:11: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |      if(xx==enx&&yy==eny)
      |         ~~^~~~~
mecho.cpp:120:20: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |      if(xx==enx&&yy==eny)
      |                  ~~^~~~~

• Subtask 1: 28 / 100