Submission #633193

#	Time	Username	Problem	Language	Result	Execution time	Memory
633193		czhang2718	Mecho (IOI09_mecho)	C++17	55 / 100	284 ms	7676 KiB

mecho

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

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define f first
#define s second
#define nl '\n'
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef pair<int, int> pii;
#define nl '\n'

const int N=800;
int n, s;
string grid[N];
int dist[N][N];
int dist2[N][N];
bool block[N][N];
int dx[]={0, 0, 1, -1};
int dy[]={1, -1, 0, 0};

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> grid[i];
    }

    auto check=[&](int t)->bool{
        queue<pair<int,int>> q;
        rep(i,0,n-1) rep(j,0,n-1){
            dist[i][j]=-1;
            block[i][j]=0;
            if(grid[i][j]=='H'){
                dist[i][j]=0;
                q.push({i,j});
            }
        }

        while(!q.empty()){
            pair<int,int> p=q.front(); 
            int x=p.first, y=p.second;
            if(dist[x][y]>t) break;
            block[x][y]=1;
            // cout << "block " << x << " " << y << "\n";
            q.pop();
            for(int k=0; k<4; k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                if(nx<0 || nx==n || ny<0 || ny==n || grid[nx][ny]=='T' || grid[nx][ny]=='D') continue;
                if(dist[nx][ny]==-1){
                    dist[nx][ny]=dist[x][y]+1;
                    q.push({nx,ny});
                }
            }
        }
        int it=0;
        queue<pair<int,int>> q2;
        rep(i,0,n-1) rep(j,0,n-1){
            if(grid[i][j]=='M') q2.push({i,j}), dist2[i][j]=0;
            else dist2[i][j]=-1;
        }
        while(true){
            it++;
            bool move=0;
            while(!q2.empty()){
                pair<int,int> p=q2.front(); 
                int x=p.first, y=p.second;
                if(dist2[x][y]>it*s) break;
                q2.pop();
                if(block[x][y]) continue;
                move=1;
                if(grid[x][y]=='D') return 1;
                for(int k=0; k<4; k++){
                    int nx=x+dx[k];
                    int ny=y+dy[k];
                    if(nx<0 || nx==n || ny<0 || ny==n || block[nx][ny] || grid[nx][ny]=='T' || grid[nx][ny]=='H' || dist2[nx][ny]!=-1) continue;
                    dist2[nx][ny]=dist2[x][y]+1;
                    q2.push({nx,ny});
                }
            }
            if(!move) break;
            while(!q.empty()){
                pair<int,int> p=q.front(); 
                int x=p.first, y=p.second;
                if(dist[x][y]>t+it) break;
                block[x][y]=1;
                q.pop();
                for(int k=0; k<4; k++){
                    int nx=x+dx[k];
                    int ny=y+dy[k];
                    if(nx<0 || nx==n || ny<0 || ny==n || grid[nx][ny]=='T' || grid[nx][ny]=='D') continue;
                    if(dist[nx][ny]==-1){
                        dist[nx][ny]=dist[x][y]+1;
                        q.push({nx,ny});
                    }
                }
            }
        }
        return 0;
    };

    int x=0;
    for(int i=10; i>=0; i--){
        if(check(x+(1<<i))) x+=(1<<i);
    }
    cout << (check(x)?x:-1);
    // rep(i,0,10) cout << check(i) << "\n";
}

• Subtask 1: 55 / 100