Submission #1224060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224060		enzy	Mecho (IOI09_mecho)	C++20	73 / 100	162 ms	13384 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
const int maxn=810;
int marc[maxn][maxn], db[maxn][maxn], mb[maxn][maxn], dx[]={1,-1,0,0}, dy[]={0,0,1,-1}, dist[maxn][maxn], m[maxn][maxn], n;
bool in(int x, int y){
    return 1<=x&&x<=n&&1<=y&&y<=n;
}
bool check(int tmp, int ix, int iy, int fx, int fy, int s){
    queue<pair<int,int>>q;
    q.push({ix,iy});
    memset(dist,-1,sizeof(dist));
    memset(m,0,sizeof(m));
    dist[ix][iy]=tmp*s;
    m[ix][iy]++;
    while(!q.empty()){
        int x=q.front().first, y=q.front().second, w=dist[x][y];
        q.pop();
        w++;
        int at=w/s;
        for(int i=0;i<4;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if(in(nx,ny)&&!marc[nx][ny]&&!m[nx][ny]&&at<db[nx][ny]){
                m[nx][ny]++;
                dist[nx][ny]=w;
                q.push({nx,ny});
            }
        }
    }
    return dist[fx][fy]!=-1;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int s; cin >> n >> s;
    queue<pair<int,int>>bees;
    int ix, iy, fx, fy;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            char c; cin >> c;
            if(c=='T') marc[i][j]=-1;
            if(c=='H'){
                bees.push({i,j});
                mb[i][j]++;
            }
            if(c=='M'){
                ix=i; iy=j;
            }
            if(c=='D'){
                fx=i; fy=j;
            }
        }
    while(!bees.empty()){
        int x=bees.front().first, y=bees.front().second;
        bees.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if(in(nx,ny)&&!mb[nx][ny]&&!marc[nx][ny]){
                db[nx][ny]=db[x][y]+1;
                mb[nx][ny]++;
                bees.push({nx,ny});
            }
        }
    }
    int l=0, r=maxn*maxn;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid,ix,iy,fx,fy,s)) l=mid;
        else r=mid-1;
    }
    if(!check(l,ix,iy,fx,fy,s)) cout << -1 << endl;
    else cout << l << endl;
}

• Subtask 1: 73 / 100