Submission #1081271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081271		Dennis_Jason	Mecho (IOI09_mecho)	C++14	100 / 100	137 ms	8896 KiB

mecho

#include <bits/stdc++.h>
#define NMAX 100001
#define pb push_back
#define eb emplace_back
#define MOD 100003
#define nl '\n'
#define INF  2147483647
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ================DEMONSTRATION===================


    =====================END========================
 */
int n,s;
int mat[805][805];
int dist[805][805];
int bee[805][805];
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};
int i_s,j_s,i_e,j_e;
queue<pii>bq;
queue<tpl>q;
bool inmat(int i,int j)
{
    return i>=1 && i<=n && j>=1 && j<=n;
}
void bear_bfs()
{
    while(!q.empty())
    {
        auto [x,y,dis]=q.front();
        q.pop();
//        cout<<x<<" "<<y<<" "<<dist[x][y]<<nl;
        if(x==i_e  && y==j_e)
        {
            return;
        }
            for(int d=0;d<4;++d)
            {
                int inou = x + di[d];
                int jnou = y + dj[d];
                int ceva=0;
                if(dis==1)
                    ceva=1;
                if (inmat(inou, jnou)
                    && (mat[inou][jnou] == 4 || mat[inou][jnou] == 3)
                    && dist[x][y] + ceva < bee[inou][jnou]
                    && dist[x][y] + ceva < dist[inou][jnou])
                {
                    dist[inou][jnou] = dist[x][y] + ceva;
                    if(ceva)
                        q.push({inou, jnou,s});
                    else
                        q.push({inou,jnou,dis-1});
                }
            }

    }
}

void bee_bfs()
{
    while(!bq.empty())
    {
        auto [x,y]=bq.front();
        bq.pop();
        for(int d=0;d<4;++d)
        {
            int inou=x+di[d];
            int jnou=y+dj[d];
            if(inmat(inou,jnou) && bee[inou][jnou]>bee[x][y]+1 && (mat[inou][jnou]==4 || mat[inou][jnou]==2))
            {
                bee[inou][jnou]=bee[x][y]+1;
                bq.push({inou,jnou});
            }
        }
    }
}
bool check(int sec)
{
    if(bee[i_s][j_s]<=sec)
        return false;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            dist[i][j]=INF;
        }
    }
    while(!q.empty())
        q.pop();
    dist[i_s][j_s]=sec;
    q.push({i_s,j_s,s});
    bear_bfs();

    return dist[i_e][j_e]!=INF;
}
signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>s;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            dist[i][j]=bee[i][j]=INF;
            char x;
            cin>>x;
            if(x=='T')
                mat[i][j]=1;
            else if(x=='M')
            {
                i_s=i;
                j_s=j;
                mat[i][j]=2;
            }
            else if(x=='D')
            {
                i_e=i;
                j_e=j;
                mat[i][j]=3;
            }
            else if(x=='G')
            {
                mat[i][j]=4;
            }
            else
            {
                bee[i][j]=0;
                bq.push({i,j});
                mat[i][j]=5;
            }
        }
    }
    bee_bfs();
//    for(int i=1;i<=n;++i)
//    {
//        for(int j=1;j<=n;++j)
//        {
//            cout<<bee[i][j]<<" ";
//        }
//        cout<<nl;
//    }
    int st=0;
    int dr=1e9;
    int ans=-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(check(mid))
        {
             ans=mid;
            st=mid+1;
        }
        else
            dr=mid-1;
    }


    cout<<ans;




    return 0;
}

Compilation message (stderr)

mecho.cpp:8: warning: "LLONG_MAX" redefined
    8 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from mecho.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      | 
mecho.cpp: In function 'void bear_bfs()':
mecho.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [x,y,dis]=q.front();
      |              ^
mecho.cpp: In function 'void bee_bfs()':
mecho.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |         auto [x,y]=bq.front();
      |              ^

• Subtask 1: 100 / 100