Submission #1281792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281792		Faisal_Saqib	Mecho (IOI09_mecho)	C++20	84 / 100	147 ms	11528 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define int ll
const int N=801;
char g[N][N];
int dist[N][N];
int d[N][N];
int sx,sy,n,s,hy,hx;
vector<pair<int,int>> hives;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
void bfs()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            dist[i][j]=1e18;
        }
    }
    queue<pair<int,int>> q;
    for(auto co:hives)
    {
        q.push(co);
        dist[co.first][co.second]=0;
    }
    while(q.size())
    {
        auto it=q.front();
        q.pop();
        int x=it.first;
        int y=it.second;
        // cout<<"Dist "<<x<<' '<<y<<' '<<dist[x][y]<<endl;
        for(int i=0;i<4;i++)
        {
            int nx=it.first+dx[i],ny=it.second+dy[i];
            if(nx>=0 and nx<n and ny>=0 and ny<n and g[nx][ny]!='T' and g[nx][ny]!='D') // bees can pass his home and trees
            {
                if(dist[nx][ny]>dist[x][y]+s)
                {
                    dist[nx][ny]=dist[x][y]+s;
                    q.push({nx,ny});
                }   
            }
        }
    }    
    // int x=hx,y=hy;
    // for(int i=0;i<4;i++)
    //     {
    //         int nx=x+dx[i],ny=y+dy[i];
    //         if(nx>=0 and nx<n and ny>=0 and ny<n and g[nx][ny]!='T') // bees can pass his home and trees
    //         {
    //             if(dist[nx][ny]+s<dist[x][y])
    //             {
    //                 dist[x][y]=dist[nx][ny]+s;
    //             }   
    //         }
    //     }
}
bool check(int tm)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            d[i][j]=1e18;
        }
    }
    // dist[sx][sy] - dt[sx][sy] for all sx ,sy and then get maximum minimum by binary search
    // {min(ti-i),cur_time} we want to maximize min(ti-i) as first priority and minimize cur_time as second priority
    // we maximize -cur_time
    d[sx][sy]=tm;

    queue<pair<int,int>> q;
    q.push({sx,sy});
    while(q.size())
    {
        auto it=q.front();
        q.pop();
        int x=it.first;
        int y=it.second;
        // cout<<"For "<<x<<' '<<y<<' '<<d[x][y]<<' '<<dist[x][y]<<endl;
        // // bees can reach the point with us or before then we are cooked
        if(d[x][y]>=dist[x][y])continue;
        for(int i=0;i<4;i++)
        {
            int nx=it.first+dx[i],ny=it.second+dy[i];
            if(nx>=0 and nx<n and ny>=0 and ny<n and g[nx][ny]!='T') // bear can go throguth tree
            {
                if(d[nx][ny]>d[x][y]+1)
                {
                    d[nx][ny]=d[x][y]+1;
                    q.push({nx,ny});
                }   
            }
        }
    }
    return d[hx][hy]!=1e18; // we can reach it thus meaning we won as bees can reach our home
}
int32_t main()
{
    cin>>n>>s;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>g[i][j];
            if(g[i][j]=='M')
            {
                sx=i,sy=j;
            }
            if(g[i][j]=='D')
            {
                hx=i,hy=j;
            }
            if(g[i][j]=='H')
            {
                hives.push_back({i,j});
            }
        }
    }
    bfs();
    int l=0,r=1e14+10;
    while(l+1<r)
    {
        ll mid=(l+r)/2;
        // cout<<"Checking for "<<mid*s<<endl;
        if(check(mid*s))
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    }
    cout<<l<<endl;
}

• Subtask 1: 84 / 100