Submission #870701

#	Time	Username	Problem	Language	Result	Execution time	Memory
870701		rsjw	Mecho (IOI09_mecho)	C++17	100 / 100	382 ms	10164 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
const int N = 1010;
char a[N][N];
int n,m;
const int xp[]={1,-1,0,0};
const int yp[]={0,0,1,-1};
int dis1[N][N],dis2[N][N];
bool check(int limit) {
    int i,j,k; queue<pii> q; pii u;
    int nx,ny,x,y;
    memset(dis1,0x3f,sizeof(dis1));
    memset(dis2,0x3f,sizeof(dis2));
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
        if(a[i][j]=='H') {
            q.push(mp(i,j));
            dis1[i][j]=0;
        }
    }
    while(!q.empty()) {
        u=q.front(); q.pop(); tie(x,y)=u;
        for(k=0;k<4;k++) {
            nx=x+xp[k],ny=y+yp[k];
            if(1<=nx&&nx<=n&&1<=ny&&ny<=n&&dis1[nx][ny]>dis1[x][y]+1&&(a[nx][ny]=='G'||a[nx][ny]=='M')) {
                dis1[nx][ny]=dis1[x][y]+1;
                q.push(mp(nx,ny));
            }
        }
    }
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
        if(a[i][j]=='M') {
            q.push(mp(i,j));
            dis2[i][j]=0;
            if(limit>=dis1[i][j]) return 0;
        }
    }
    
    while(!q.empty()) {
        u=q.front(); q.pop(); tie(x,y)=u;
        for(k=0;k<4;k++) {
            nx=x+xp[k],ny=y+yp[k];
            if(1<=nx&&nx<=n&&1<=ny&&ny<=n&&dis2[nx][ny]>dis2[x][y]+1&&a[nx][ny]!='T') {
                if((dis2[x][y]+1)/m+limit<dis1[nx][ny]) {
                    dis2[nx][ny]=dis2[x][y]+1;
                    q.push(mp(nx,ny));
                }
            }
        }
    }
    for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
        if(a[i][j]=='D') {
            if(dis2[i][j]!=0x3f3f3f3f) {
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>(a[i]+1);
    int l=0,r=1000005,mid;
    while(l<=r) {
        mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    } cout<<r<<endl;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:62:11: warning: unused variable 'j' [-Wunused-variable]
   62 |     int i,j;
      |           ^

• Subtask 1: 100 / 100