Submission #263486

#	Time	Username	Problem	Language	Result	Execution time	Memory
263486		uacoder123	Mecho (IOI09_mecho)	C++14	100 / 100	212 ms	7032 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)

typedef long long int lli;
typedef pair <int, int> df;
typedef vector <int> vi;

int te,n,s;pair<int,int> pob,poh;
char grid[800][800];
int tobc[800][800];
int visited[800][800];
pair<int,int> movearr[] = {{0,-1},{1,0},{0,1},{-1,0}};

int canmove(const pair<int,int>& pos, const pair<int,int>& ptom, const int& bearob)
{
    if(ptom.S>=n||ptom.S<0||ptom.F>=n||ptom.F<0||grid[ptom.F][ptom.S]=='T')
        return(0);
    if(bearob==0&&grid[ptom.F][ptom.S]=='D')
        return(0);
  
    return(1);
}

int check(int t,int r)
{
    if(tobc[pob.F][pob.S] <= t) return 0;
    memset(visited, 0, sizeof(visited));
    int maccom=0,step=0;
    queue<pair<int,int>> sp1,sp2;
    sp1.push(pob);
    visited[pob.F][pob.S]=1;
    while(sp1.size()!=0)
    {
        pair<int,int> pos=sp1.front();
        for(int i=0;i<4;++i)
        {
            int x=pos.F+movearr[i].F,y=pos.S+movearr[i].S;
            if(canmove(pos,{x, y},1) && !visited[x][y] )
            {
                if(tobc[x][y]>t&&(step!=s-1||tobc[x][y]!=t+1))
                {
                    sp2.push({x,y});
                    visited[x][y]=1;
                    if(mp(x,y)==poh)
                    {
                        maccom++;
                    }
                }
            }
        }
        sp1.pop();
        if(sp1.size()==0)
        {
            step = (1 + step)%s;
            if(!step) ++t;
            swap(sp1,sp2);
        }
    }
    return(maccom);
}

void bfs1(vector<pair<int,int>> pos_vec)
{
    memset(visited, 0, sizeof(visited));
    queue<pair<int,int>> q;
    for(uint i=0;i<pos_vec.size();++i) 
    {
        q.push(pos_vec[i]);
        visited[pos_vec[i].F][pos_vec[i].S]=1;
    }
        
    while(q.size())
    {
        pair<int,int> pos=q.front();
        for(int i=0;i<4;++i)
        {
            int x=pos.F+movearr[i].F,y=pos.S+movearr[i].S;
            if(canmove(pos,{x,y},0) && !visited[x][y])
            {
                q.push({x,y});
                visited[x][y]=1;
                tobc[x][y]=min(tobc[x][y],tobc[pos.F][pos.S]+1);
            }
        }
        q.pop();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    te=1;
     cin>>n>>s;   
     vector<pair<int,int>> pobees; 
     for(int i=0;i<n;++i)
     {
        for(int i1=0;i1<n;++i1)
            {
                tobc[i][i1]=650000;
                cin>>grid[i][i1];
                if(grid[i][i1]=='M')
                    pob={i,i1};
                else if(grid[i][i1]=='D')
                    poh={i,i1};
                else if(grid[i][i1]=='H')
                   {
                    pobees.pb(mp(i,i1));
                    tobc[i][i1]=0;
                   }
            }
     }   

     bfs1(pobees);
     int r=n*n,l=0,ans=-1;
     while(l<=r)
     {
        int mid=(l+r+1)/2;
        if(check(mid,r))
        {
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
     }
     cout<<ans<<endl;
    return 0;
}

• Subtask 1: 100 / 100