제출 #587486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587486		Agnimandur	Mecho (IOI09_mecho)	C++17	100 / 100	359 ms	6356 KiB

mecho

#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define si set<int>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define add push_back
#define REP(i,a) for (int i = 0; i < (a); i++)
using namespace std;
 
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int INF = 1005000000; 
//const ll MOD = 1000000007LL;
const ll MOD = 998244353LL;
 
int ni() {
    int x; cin >> x;
    return x;
}
 
ll nl() {
    ll x; cin >> x;
    return x;
}
 
double nd() {
    double x; cin >> x;
    return x;
}

string next() {
    string x; cin >> x;
    return x;
}

int N,S;
char grid[800][800];
pii mecho1;
pii mecho2;
vector<pii> hives;
vvi dirs = {{-1,0},{1,0},{0,-1},{0,1}};

void printDist(vvi dist) {
    REP(i,N) REP(j,N) {
        if (dist[i][j]==INF)
            cout << "I";
        else
            cout << dist[i][j];
        if (j==N-1) cout << '\n';
    }
}

bool solve(int headstart) {
    vvi mechoDist(N,vi(N,INF));
    queue<pii> mechoQ;
    mechoDist[mecho1.first][mecho1.second] = 0;
    mechoQ.push(mecho1);

    vvi beeDist(N,vi(N,INF));
    queue<pii> beeQ;
    for (pii& hive: hives) {
        beeDist[hive.first][hive.second] = 0;
        beeQ.push(hive);
    }
    while (!beeQ.empty()) {
        pii p = beeQ.front();
        if (beeDist[p.first][p.second] == headstart) break;
        beeQ.pop();
        for (vi& dir: dirs) {
            int newR = p.first+dir[0];
            int newC = p.second+dir[1];
            if (newR >= 0 && newR < N && newC >= 0 && newC < N && beeDist[newR][newC]==INF && grid[newR][newC] != 'T' && grid[newR][newC] != 'D') {
                beeDist[newR][newC] = beeDist[p.first][p.second]+1;
                beeQ.push({newR,newC});
            }
        }
    }

    int travel = 0;
    while (!mechoQ.empty()) {
        travel += S;
        //mecho moves up to travel spaces from the origin.
        while (!mechoQ.empty()) {
            pii p = mechoQ.front();
            if (mechoDist[p.first][p.second] == travel) break;
            mechoQ.pop();
            if (beeDist[p.first][p.second] < INF) {
                //bees control this cell already
                continue;
            }
            for (vi& dir: dirs) {
                int newR = p.first+dir[0];
                int newC = p.second+dir[1];
                if (newR >= 0 && newR < N && newC >= 0 && newC < N && mechoDist[newR][newC]==INF && grid[newR][newC] != 'T' && grid[newR][newC] != 'H' && beeDist[newR][newC] == INF) {
                    mechoDist[newR][newC] = mechoDist[p.first][p.second]+1;
                    mechoQ.push({newR,newC});
                }
            }
        }

        headstart++;
        while (!beeQ.empty()) {
            pii p = beeQ.front();
            if (beeDist[p.first][p.second] == headstart) break;
            beeQ.pop();
            for (vi& dir: dirs) {
                int newR = p.first+dir[0];
                int newC = p.second+dir[1];
                if (newR >= 0 && newR < N && newC >= 0 && newC < N && beeDist[newR][newC]==INF && grid[newR][newC] != 'T' && grid[newR][newC] != 'D') {
                    beeDist[newR][newC] = beeDist[p.first][p.second]+1;
                    beeQ.push({newR,newC});
                }
            }
        }
    }

    if (mechoDist[mecho2.first][mecho2.second] < INF) {
        //he can reach his home!
        return true;
    } else {
        return false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    N = ni();
    S = ni();
    REP(i,N) {
        string s = next();
        REP(j,N) {
            grid[i][j] = s[j];
            if (grid[i][j]=='M')
                mecho1 = {i,j};
            else if (grid[i][j]=='D')
                mecho2 = {i,j};
            else if (grid[i][j]=='H')
                hives.add({i,j});
        }
    }

    int lo = 0;
    int hi = N*N;
    if (!solve(0)) {
        //mecho can't reach the house ever
        cout << -1;
        return 0;
    }
    while (lo < hi) {
        int m = (lo+hi+1)/2;
        if (solve(m)) {
            lo = m;
        } else {
            hi = m-1;
        }
    }
    cout << lo;
}

• Subtask 1: 100 / 100