제출 #711007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711007		tgp072	Mecho (IOI09_mecho)	C++14	100 / 100	241 ms	10468 KiB

mecho

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>
#include <map>
#include <string>
#include <tuple>
#include <numeric>
#include <climits>
#include <bitset>
#include <iomanip>
#include <random>
#include <ctime>
using namespace std;

typedef long long ll;

const ll INF = 1e14;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 1;

ll fact[MAXN];
void precompute()
{
   fact[0] = 1;
   for (ll i = 1; i < MAXN; i++) {
       fact[i] = (i * fact[i - 1]) % MOD;
   }
}

ll powmod(ll a, ll b){
    a %= MOD;
    if (a == 0) return 0;
    ll product = 1;
    while(b > 0){
        if (b&1){    // you can also use b % 2 == 1
            product *= a;
            product %= MOD;
            --b;
        }
        a *= a;
        a %= MOD;
        b /= 2;    // you can also use b >> 1
    }
    return product;
}

ll max(ll a, ll b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

ll min(ll a, ll b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

//calculates the inverse of a number mod MOD
ll inv(ll a) {
    return powmod(a, MOD - 2);
}

//Observation: We can binary search on the answer. This is b/c if the bear is able to eat honey for x minutes before leaving and succesfully making it back home, the bear would have also been able to eat honey for x-1 minutes
//before succesfully making it home. So we'll binary search on the answer, printing -1 if it's impossible to make it even if the bear leaves immediately.

//How do we check if a given time works? Let's do some precomputation. Let's run a multi-source BFS at the beginning of the program to compute the minimum distance from the hives to every grassy node without crossing
//trees or the bear's destination.

//Now to check if a given time works, we'll run a second BFS from the start node. Instead of counting the minimum distance in minutes, we'll count it in steps. For example if we start at x minutes, we'll assume we've started
//at our source node with s*x steps. Now at each cell, we'll check if the #of minutes it took the bear to get to that cell is less than the #of minutes it took for the bees to get there. If the #of minutes it took the bear
//is greater than or equal to that of the #of minutes for the bees, then we can't move on from that cell since it would already have been visited by bees. The reason why the equality case is also punished is b/c of the
//nature of the problem. First the bear will move at most s steps, and then the bees will move. So if the #of minutes is the same, the bear will still get caught. This also motivates us to count
//the number of minutes it took the bear to reach cell [i][j] as floor(K_ij/s) where K_ij is the minimum number of steps to reach cell [i][j]. This is motivated by similar logic to the above observation.
//So we'll keep running this BFS until we somehow manage to make it to the destination or we don't

//State allows us to store a cell row, cell col, and min distance
struct State{
    ll cr, cc, cd;
};

//Direction arrays used to iterate over the 4 cardinal directions.
ll dr[4] = {0, 1, 0, -1};
ll dc[4] = {1, 0, -1, 0};

void solve(ll ca) {
    //Read in input
    ll n, s;
    cin >> n >> s;
    
    char grid[n][n];
    pair<ll, ll> sc; //Store coordinates of the start
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'M') {
                sc = {i, j};
            }
        }
    }
    
    //dist[i][j] is the min distance from any hive to cell [i][j]
    ll dist[n][n];
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            dist[i][j] = INF;
        }
    }
    
    //Run multi-source BFS from the hives
    queue<State> q;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (grid[i][j] == 'H') {
                q.push({i, j, 0});
            }
        }
    }
    
    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        
        if (dist[cur.cr][cur.cc] <= cur.cd) {
            continue;
        }
        
        dist[cur.cr][cur.cc] = cur.cd;
        
        for (ll k = 0; k < 4; k++) {
            ll nr = cur.cr + dr[k];
            ll nc = cur.cc + dc[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] != 'T' && grid[nr][nc] != 'D' && grid[nr][nc] != 'H') {
                q.push({nr, nc, cur.cd+1});
            }
        }
    }
    
    //Binary search on the largest amount of time the bear can wait before departing
    ll lo = 0; ll hi = INF;
    lo--;
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1)/2;
        bool works = false;
        
        bool visited[n][n];
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n; j++) {
                visited[i][j] = false;
            }
        }
        
        //Run 2nd BFS from source node
        queue<State> q2;
        q2.push({sc.first, sc.second, s*mid});
        while (!q2.empty()) {
            State cur = q2.front();
            q2.pop();
            
            if (grid[cur.cr][cur.cc] == 'D') {
                works = true;
                break;
            }
            
            //Calculate the #of minutes it took to reach the cell and make sure the bees won't catch the bear
            ll nummin = cur.cd/s;
            if (nummin >= dist[cur.cr][cur.cc]) {
                continue;
            }
            
            //Obviously don't visit an already visited cell
            if (visited[cur.cr][cur.cc]) {
                continue;
            }
            visited[cur.cr][cur.cc] = true;
            
            for (ll k = 0; k < 4; k++) {
                ll nr = cur.cr + dr[k];
                ll nc = cur.cc + dc[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] != 'T') {
                    q2.push({nr, nc, cur.cd+1});
                }
            }
        }
        
        if (works) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    
    //Print the largest amount of time the bear could have stalled, or -1 if it's impossible for the bear to make it back
    cout << lo << endl;
}

int main() {
    mt19937 rng(0);
    // Fast IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
/*
    freopen("gravity.in", "r", stdin);
    freopen("gravity.out", "w", stdout);
    */
    ll t = 1;
    //cin >> t;
    
    ll co = 0;
    while (t--) {
        solve(co);
        co++;
    }
}

• Subtask 1: 100 / 100