제출 #482481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482481		asdf1234coding	Mecho (IOI09_mecho)	C++14	100 / 100	179 ms	6292 KiB

mecho

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define MOD (ll) (1e9+7)
#define pii pair<int,int>
#define ff first
#define ss second

int n,s; 
pii start,finish;
string board[801];
vector<vector<int>> beedist(801, vector<int>(801, -1));
queue<pii> bees;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool inBounds(pii asdf) {
    int x=asdf.ff; int y=asdf.ss;
    return (x>=0 && x<n && y>=0 && y<n && board[x][y]!='T');
}

void beeDist() {
    while(!bees.empty()) {
        auto curr = bees.front(); bees.pop();
        for(int i=0; i<4; i++) {
            pii next = {curr.first+dx[i], curr.second+dy[i]};
            if(inBounds(next) && beedist[next.ff][next.ss] == -1 && board[next.ff][next.ss]!='D') {
                beedist[next.ff][next.ss] = beedist[curr.ff][curr.ss] + s;
                bees.push(next);
            }
        }
    }
}

bool test(int delay) {
    vector<vector<int>> dist(801, vector<int>(801, -1));
    if(delay*s>=beedist[start.ff][start.ss]) {
        return false;
    }
    queue<pii> q; q.push(start);
    dist[start.ff][start.ss] = delay*s;
    while(!q.empty()) {
        auto curr = q.front(); q.pop();
        if(curr == finish) {
            return true;
        }
        for(int i=0; i<4; i++) {
            pii next = {curr.ff+dx[i], curr.ss+dy[i]};
            if(inBounds(next)&&((dist[curr.ff][curr.ss]+1)<beedist[next.ff][next.ss])&&dist[next.ff][next.ss]==-1) {
                dist[next.ff][next.ss] = dist[curr.ff][curr.ss]+1;
                q.push(next);
            }
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin>>n>>s;
    for(int i=0; i<n; i++) {
        cin>>board[i];
        for(int j=0; j<n; j++) {
            if(board[i][j] == 'M') {
                start.ff = i;
                start.ss = j;
            } else if (board[i][j] == 'D') {
                finish.ff = i;
                finish.ss = j;
            } else if (board[i][j] == 'H') {
                beedist[i][j] = 0;
                bees.push({i,j});
            }
        }
    }

    beeDist();
    // for(int i=0; i<n; i++) {
    //     for(int j=0; j<n; j++) {
    //         cout<<beedist[i][j]<<' ';
    //     }
    //     cout<<endl;
    // }
    // cout<<test(0)<<endl;
    // cout<<test(1)<<endl;
    // cout<<test(2)<<endl;
    // cout<<test(3)<<endl;

    beedist[finish.ff][finish.ss] = n*n*s;

    //binsearch :D
    int lo = -1; int hi = 2*n*n;
    while(hi-lo>1) {
        int mid = (lo+hi)>>1;
        if(test(mid)) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    cout<<lo<<endl;
    return 0;
}

• Subtask 1: 100 / 100