제출 #710994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710994		tgp072	Mecho (IOI09_mecho)	C++14	100 / 100	240 ms	10444 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);
}

struct State{
    ll cr, cc, cd;
};

ll dr[4] = {0, 1, 0, -1};
ll dc[4] = {1, 0, -1, 0};

void solve(ll ca) {
    ll n, s;
    cin >> n >> s;
    
    char grid[n][n];
    pair<ll, ll> sc;
    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};
            }
        }
    }
    
    ll dist[n][n];
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            dist[i][j] = INF;
        }
    }
    
    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});
            }
        }
    }
    /*
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                cout << -1 << " ";
                continue;
            }
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }*/
    
    ll lo = 0; ll hi = INF;
    lo--;
    while (lo < hi) {
        ll mid = lo + (hi - lo + 1)/2;
        //mid = 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;
            }
        }
        
        queue<State> q2;
        q2.push({sc.first, sc.second, s*mid});
        
        while (!q2.empty()) {
            State cur = q2.front();
            q2.pop();
            
           /*if (cur.cr == 3 && cur.cc == 6) {
                cout << "I AM HERE" << endl;
            }*/
            if (grid[cur.cr][cur.cc] == 'D') {
                works = true;
                break;
            }
            
            /*if (cur.cr == 3 && cur.cc == 6) {
                cout << "I AM HERE" << endl;
            }*/
            
            ll nummin = cur.cd/s;
            if (nummin >= dist[cur.cr][cur.cc]) {
                continue;
            }
            
            if (visited[cur.cr][cur.cc]) {
                continue;
            }
            
            //cout << cur.cr << " " << cur.cc << endl;
            
            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;
        }
        
        /*cout << works << endl;
        return;*/
    }
    
    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