제출 #549457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549457		beaconmc	Mecho (IOI09_mecho)	C++14	100 / 100	418 ms	13020 KiB

mecho

#include <bits/stdc++.h>


typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll grid[801][801];
ll visited[801][801];
ll n,s;
vector<vector<ll>> hives;
vector<ll> start;
vector<ll> endd;
vector<vector<ll>> ops = {{0,1}, {0,-1}, {1,0}, {-1,0}};

void bfsinit(){
    queue<vector<ll>> d;
    for (auto&i : hives){
        d.push({i[0], i[1], 0});
    }
    while (d.size()){
        vector<ll> node = d.front();;
        d.pop();
        for (auto&i : ops){
            ll a = node[0] + i[0];
            ll b = node[1] + i[1];
            if (0<=a && a<n && 0<=b && b<n){
                if (grid[a][b] == -3){
                    d.push({a,b,node[2]+1});
                    grid[a][b] = node[2]+1;
                }

            }
        }

    }

}

bool test(ll time){
    queue<vector<ll>> d;
    if (grid[start[0]][start[1]] <= time){
        return false;
    }
    FOR(i,0,n){
        FOR(j,0,n){
            visited[i][j] = false;
        }
    }
    d.push({start[0], start[1], 0});
    while (d.size()){
        vector<ll> node = d.front();
        d.pop();
        if (node[0]==endd[0] && node[1] == endd[1]){
            return true;
        }
        for (auto&i : ops){
            ll a = node[0]+i[0];
            ll b = node[1] + i[1];
            if (0<=a && a<n && 0<=b && b<n && !(visited[a][b])){
                if (grid[a][b] == -2) continue;
                if (grid[a][b] == -1 || grid[a][b] > time+(node[2]+1)/s){
                    d.push({a,b,node[2]+1});
                    visited[a][b] = true;
                }
            }

        }
    }
    return false;
}


int main(){
    fast();
    cin >> n >> s;
    FOR(i,0,n){
        string sus;
        cin >> sus;
        FOR(j,0,n){
            grid[i][j] = sus[j];
        }
    }
    FOR(i,0,n){
        FOR(j,0,n){
            if (grid[i][j] == 'T') grid[i][j] = -2;
            else if (grid[i][j] == 'D'){
                grid[i][j] = -1;
                endd = {i,j};
            } 
            else if (grid[i][j] == 'H'){
                grid[i][j] = 0;
                hives.push_back({i,j});
            } 
            else if (grid[i][j] == 'M'){
                start = {i,j};
                grid[i][j] = -3;
            }
            else{
                grid[i][j] = -3;
            }
        }
    }
    bfsinit();
    ll lo = -1;
    ll hi = n*n;
    while (lo<hi){
        ll mid = lo+(hi-lo+1)/2;
        if (test(mid)) lo = mid;
        else hi = mid-1;
    }
    cout << lo;

}

• Subtask 1: 100 / 100