제출 #571362

#제출 시각아이디문제언어결과실행 시간메모리
571362f4t4ntMecho (IOI09_mecho)C++11
84 / 100
323 ms16864 KiB
#include <algorithm> #include <cmath> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iostream> #include <iomanip> #include <iterator> #include <list> #include <map> #include <math.h> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <stdio.h> #include <string> #include <tuple> #include <unordered_set> #include <utility> #include <vector> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using ch = char; using str = string; #define pb push_back #define elif else if #define sz(C) (ll) C.size() #define mp make_pair #define mt make_tuple #define flip(C) reverse(C.begin(), C.end()) #define ssort(C) sort(C.begin(), C.end()) #define rsort(C) sort(C.begin(), C.end(), greater<>()) #define FOR(x, e) for(ll x = 0; x < (ll) e; x++) #define FORR(x, e) for(ll x = (ll) e - 1; x >= 0; x--) #define FOB(x, b, e) for(auto x = b; x < e; x++) #define FOI(x, e, i) for(ll x = 0; x < (ll) e; x += (ll) i) #define FOBI(x, b, e, i) for(ll x = (ll) b; x < (ll) e; x += (ll) i) #define FORE(x, C) for(auto &x : C) #ifdef LOCAL #include "tester.cpp" #define main test_main extern istringstream fin; extern ostringstream fout; string test_file_name = "tests"; #define cin fin #define cout fout #endif vector<int> di { -1, 0, 1, 0}; vector<int> dj { 0, -1, 0, 1}; void fill_b(ll &n, vector<vector<char>> &g, queue<pair<ll, ll>> &bfs_b, vector<vector<ll>> &d_b) { while(sz(bfs_b)) { ll i0 = bfs_b.front().first, j0 = bfs_b.front().second; bfs_b.pop(); FOR(k, 4) { ll i1 = i0 + di[k], j1 = j0 + dj[k]; if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue; if(g[i1][j1] == 'T' || g[i1][j1] == 'D') continue; if(d_b[i1][j1] != 1e18) continue; d_b[i1][j1] = d_b[i0][j0] + 1; bfs_b.push({i1, j1}); } } } bool valid(ll &mid, ll &n, ll &s, vector<vector<ll>> &d_b, vector<vector<char>> &g, queue<pair<ll, ll>> bfs_m, vector<vector<ll>> d_m) { while(sz(bfs_m)) { ll i0 = bfs_m.front().first, j0 = bfs_m.front().second, d = d_m[i0][j0] + 1; bfs_m.pop(); FOR(k, 4) { ll i1 = i0 + di[k], j1 = j0 + dj[k]; if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue; if(g[i1][j1] == 'T') continue; if(d_m[i1][j1] != 1e18) continue; if(d_b[i1][j1] <= mid + d / s) continue; if(g[i1][j1] == 'D') return true; d_m[i1][j1] = d; bfs_m.push({i1, j1}); } } return false; } int main() { ll n, s, lo = 0; cin >> n >> s; ll hi = n * n; vector<vector<char>> g(n, vector<char>(n)); vector<vector<ll>> d_b(n, vector<ll>(n, 1e18)), d_m(n, vector<ll>(n, 1e18)); queue<pair<ll, ll>> bfs_b, bfs_m; FOR(i, n) FOR(j, n) { cin >> g[i][j]; if(g[i][j] == 'H') { bfs_b.push({i, j}); d_b[i][j] = 0; } elif(g[i][j] == 'M') { bfs_m.push({i, j}); d_m[i][j] = 0; } } fill_b(n, g, bfs_b, d_b); if(!valid(lo, n, s, d_b, g, bfs_m, d_m)) { cout << "-1\n"; return 0; } while(hi - lo > 0) { ll mid = lo + (hi - lo + 1) / 2; if(valid(mid, n, s, d_b, g, bfs_m, d_m)) lo = mid; else hi = mid - 1; } cout << lo << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...