제출 #1283522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283522		efeg	Mecho (IOI09_mecho)	C++20	84 / 100	147 ms	7012 KiB

mecho

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


//#define int long long

typedef tuple<int,int,int> iii; 
const int maxN = 810; 



char a[maxN][maxN]; 
int dist[maxN][maxN],vis[maxN][maxN]; 
int n,s; 

int mi,mj; 

int dX[] = {-1,0,0,1}; 
int dY[] = {0,1,-1,0}; 

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> s;
    queue<iii> q; 

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> a[i][j]; 
            dist[i][j] = INT_MAX; 
            if (a[i][j] == 'H'){
                q.push({i,j,0}); 
            }
            else if (a[i][j] == 'M'){
                mi = i; mj = j; 
            }
        }
    }

    auto check1 = [&](int i,int j) -> bool {
        if (
            i > -1 && j > -1 &&
            i < n && j < n && 
            (a[i][j] == 'G' || a[i][j] == 'M') && 
            dist[i][j] == INT_MAX 
        ) return true; 
        return false; 
    }; 


    while (!q.empty()){
        int d,i,j; tie(i,j,d) = q.front();
        q.pop(); 
        if (dist[i][j] != INT_MAX) continue; 
        dist[i][j] = d;  

        for (int x = 0; x < 4; x++){
            int toi = dX[x] + i,toj = dY[x] + j; 
            if (check1(toi,toj)){
                q.push({toi,toj,d+1}); 
            }
        }
    }

    auto check2 = [&](int i,int j,int step,int m){
        if (i > -1 && j > -1 && 
            i < n && j < n && vis[i][j] == -1 && 
            a[i][j] != 'T' && m + step / s < dist[i][j]  
        ) return true;
        return false; 
    }; 


    auto bincheck = [&](int m) -> bool {
        memset(vis,-1,sizeof(vis)); 
        queue<iii> q; 
        //if (check2(mi,mj,0,m)) 
        q.push({mi,mj,0}); 
        bool arrived = false; 

        while (!q.empty()){
            int i,j,step; tie(i,j,step) = q.front(); q.pop(); 
            if (vis[i][j] != -1) continue; 
            if (a[i][j] == 'D'){
                arrived = true;
                break; 
            }
            vis[i][j] = 1; 
 
            for (int x = 0; x < 4; x++){
                int toi = dX[x] + i,toj = dY[x] + j;
                if (check2(toi,toj,step+1,m)){
                    q.push({toi,toj,step+1}); 
                } 
            }
        }
        return arrived; 

    }; 


    int l = 0,r = 1e9,ans = -1;
    while (l <= r){
        int m = (l+r) / 2; 
        if (bincheck(m)){
            ans = m; 
            l = m+1; 
        }
        else r = m-1; 
    }

    cout << ans << endl; 
    return 0; 
}

• Subtask 1: 84 / 100