제출 #633197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633197		czhang2718	Mecho (IOI09_mecho)	C++17	100 / 100	184 ms	6296 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 bee[N][N];
int dist[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){
            if(grid[i][j]=='M'){
                if(bee[i][j]<=t) return 0;
                q.push({i,j});
                dist[i][j]=0;
            }
            else dist[i][j]=1e9;
        }
        while(!q.empty()){
            pair<int,int> p=q.front(); q.pop();
            int x=p.first, y=p.second;
            if(grid[x][y]=='D') return 1;
            // cout << x << y << '\n';
            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' || dist[nx][ny]!=1e9) continue;
                if(bee[nx][ny]>t+(dist[x][y]+1)/s){
                    dist[nx][ny]=dist[x][y]+1;
                    q.push({nx,ny});
                }
            }
        }
        return 0;
    };

    queue<pair<int,int>> q;
    rep(i,0,n-1) rep(j,0,n-1){
        if(grid[i][j]=='H') q.push({i,j}), bee[i][j]=0;
        else bee[i][j]=1e9;
    }
    while(!q.empty()){
        pair<int,int> p=q.front(); 
        int x=p.first, y=p.second;
        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' || bee[nx][ny]!=1e9) continue;
            bee[nx][ny]=bee[x][y]+1;
            q.push({nx,ny});
        }
    }
    // rep(i,0,n-1){
    //     rep(j,0,n-1){
    //         cout << bee[i][j] << " ";
    //     }
    //     cout << nl;
    // }

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

• Subtask 1: 100 / 100