Submission #1308207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308207		Warinchai	Mecho (IOI09_mecho)	C++20	100 / 100	374 ms	26940 KiB

mecho

#include<bits/stdc++.h>
#define int long long
using namespace std;

string s[1005];
int ar[1005][1005];
int vis[1005][1005];
int bear[1005][1005],bee[1005][1005];
int val[1005][1005];
pair<int,int>dir[4]={
    {0,1},{1,0},{0,-1},{-1,0}
};
int inf=1e9;
int n,k;
pair<int,int>st,en;

int check(int m){
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=0,bear[i][j]=inf;
    queue<pair<int,int>>q;
    q.push(st);
    vis[st.first][st.second]=1;
    bear[st.first][st.second]=0;
    int cur=m;
    //cerr<<"workk\n";
    while(!q.empty()){
        auto x=q.front();
        q.pop();
        //cerr<<"go:"<<x.first<<" "<<x.second<<" "<<bear[x.first][x.second]<<"\n";
        for(int i=0;i<4;i++){
            int xx=x.first+dir[i].first;
            int yy=x.second+dir[i].second;
            int tme=bear[x.first][x.second];
            if(xx<1||xx>n||yy<1||yy>n||vis[xx][yy]||ar[xx][yy]==0||m+(tme)/k>=bee[x.first][x.second])continue;
            bear[xx][yy]=bear[x.first][x.second]+1;
            q.push({xx,yy});
            vis[xx][yy]=1;
        }
    }
    return vis[en.first][en.second];
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>s[i];
    vector<pair<int,int>>v;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            bear[i][j]=bee[i][j]=inf;
            if(s[i-1][j-1]=='T');
            else if(s[i-1][j-1]=='G')ar[i][j]=1;
            else if(s[i-1][j-1]=='M')st={i,j},ar[i][j]=1;
            else if(s[i-1][j-1]=='D')en={i,j},ar[i][j]=2;
            else v.push_back({i,j});
        }
    }
    queue<pair<int,int>>q;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=0;
    for(auto x:v){
        q.push(x);
        vis[x.first][x.second]=1;
        bee[x.first][x.second]=0;
    }
    while(!q.empty()){
        auto x=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=x.first+dir[i].first;
            int yy=x.second+dir[i].second;
            if(xx<1||xx>n||yy<1||yy>n||vis[xx][yy]||ar[xx][yy]!=1)continue;
            bee[xx][yy]=bee[x.first][x.second]+1;
            q.push({xx,yy});
            vis[xx][yy]=1;
        }
    }
    //cerr<<"work\n";
    int l=0,r=1e9,ans=-1;
    while(l<=r){
        int m=(l+r)/2;
        //cerr<<"m:"<<m<<"\n";
        if(check(m)){
            ans=m;
            l=m+1;
        }else{
            r=m-1;
        }
    }
    cout<<ans;

    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cerr<<bear[i][j]<<"\t";
        cerr<<"\n";
    }
    cerr<<"\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cerr<<bee[i][j]<<"\t";
        cerr<<"\n";
    }
    cerr<<"\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cerr<<val[i][j]<<"\t";
        cerr<<"\n";
    }
    cerr<<"\n";*/
}

• Subtask 1: 100 / 100