Submission #440357

#TimeUsernameProblemLanguageResultExecution timeMemory
440357KarliverMecho (IOI09_mecho)C++14
53 / 100
445 ms6240 KiB
#include <bits/stdc++.h> #define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x) #define all(v) (v).begin(), (v).end() using namespace std; #define forn(i,n) for (int i = 0; i < (n); ++i) #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i) using ll = long long; int mod = (ll)1e9 + 7; #define PI acos(-1) typedef pair<int, int> pairs; const int INF = 1e9 + 1; const int N = 2e5 + 100; const double eps = 1e-7; template <class T> using V = vector<T>; template <class T> using VV = V<V<T>>; template <typename XPAX> void ckma(XPAX &x, XPAX y) { x = (x < y ? y : x); } template <typename XPAX> void ckmi(XPAX &x, XPAX y) { x = (x > y ? y : x); } void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) void solve() { int n; cin >> n; int s; cin >> s; queue<pairs> q; V<string> c(n); forn(i, n) { cin >> c[i]; //debug(c[i]); } auto valid = [&](int i, int j) { return (i < n && j < n && i > -1 && j > -1 && c[i][j] != 'T'); }; int sx, sy; int tx, ty; V<pairs> directions{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; auto dv = [&](int x) { return x / s; }; VV<int> bee(n, V<int>(n, INF)); forn(i, n) forn(j, n) { if(c[i][j] == 'H') { q.push({i, j}); bee[i][j] = 0; } if(c[i][j] == 'D') { tx = i; ty = j; } if(c[i][j] == 'M') { sx = i; sy = j; } } // debug(bee); while(q.size()) { int i = q.front().first; int j = q.front().second; q.pop(); for(auto dir : directions) { int ei = i + dir.first; int ej = j + dir.second; if(valid(ei, ej) && bee[ei][ej] == INF && c[ei][ej] == 'G') { bee[ei][ej] = bee[i][j] + 1; q.push({ei, ej}); } } } auto ck = [&](int mid) -> bool { VV<int> dis(n, V<int>(n, -1)); dis[sx][sy] = 0; queue<pairs> q; q.push({sx, sy}); while(q.size()) { int i = q.front().first; int j = q.front().second; q.pop(); for(auto dir : directions) { int ei = i + dir.first; int ej = j + dir.second; if(valid(ei, ej) && dis[ei][ej] == -1 && bee[ei][ej] > dv(dis[i][j] + 1) + mid) { dis[ei][ej] = dis[i][j] + 1; q.push({ei, ej}); } } } //debug(dis); return (dis[tx][ty] != -1); }; int low = 0; int high = 1002; while(low < high) { int mid = (low + high + 1) / 2; if(ck(mid)) low = mid; else high = mid - 1; } cout << (ck(low) ? low : -1) << '\n'; } void test_case() { int t; cin >> t; forn(p, t) { //cout << "Case #" << p + 1 << ": "; solve(); } } int main() { ios::sync_with_stdio(false); cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...