Submission #1284297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284297		seven_mark	Mecho (IOI09_mecho)	C++20	84 / 100	153 ms	11232 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 


// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// gp_hash_table<int, int, chash> id;

template <typename T> std::ostream &operator<<(std::ostream &stream, const vector<T> &vec) {for (size_t i = 0; i < vec.size(); i++) { stream << vec[i]; if (i != vec.size() - 1) stream << ' '; }; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, vector<T> &vec) {for (T &x : vec) stream >> x; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, array<T, 2> &arr) {stream >> arr[0] >> arr[1]; return stream; } template <typename T> std::ostream &operator<<(std::ostream &stream, const array<T, 2> &arr) {stream << '(' << arr[0] << ", " << arr[1] << ')'; return stream; } template <typename T, typename U> std::ostream &operator<<(std::ostream &stream, const pair<T, U> &pr) {stream << pr.first << ' ' << pr.second; return stream; } template <typename T, typename U> std::istream &operator>>(std::istream &stream, pair<T, U> &pr) {stream >> pr.first >> pr.second; return stream; } template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string &s) { return '"' + s + '"'; } string to_string(char c) {string s; s += c; return s; } string to_string(const char *s) { return to_string((string)s); } string to_string(bool b) { return (b ? "1" : "0"); } string to_string(vector<bool> v) {bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) {string res = ""; for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) {bool first = true; string res = "{"; for (const auto &x : v) {if (!first) {res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cout << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cout << " " << to_string(H); debug_out(T...); }
#define ll long long
#define int long long
#define lld long double
#define ull unsigned long long
#define endl '\n'
#define sp ' '
#define pb push_back
#define ai(zzz) array<int, zzz>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vll vector<ll>
#define vvi vector<vi>
#define msb(zzz) (1<<(31-__builtin_clz(zzz)))
#define msbll(zzz) (1<<(63-__builtin_clzll(zzz)))
#define all(zzz) zzz.begin(),zzz.end()
#define rall(zzz) zzz.rbegin(),zzz.rend()
#define f first
#define s second
#define FORN(i, n) for(i=0;i<n;i++)
#define OUT(zzz) for(auto zzzz: zzz) cout << zzzz << ' ';cout<<endl;
#define OUT2(zzz) for (auto &zzzzz : zzz) {OUT(zzzzz)}
#define IN(zzz) for (auto &zzzz : zzz) cin>>zzzz;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#define startTimer std::chrono::time_point<std::chrono::high_resolution_clock> start, end;start = std::chrono::high_resolution_clock::now();
#define endTimer end = std::chrono::high_resolution_clock::now();ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();cerr << "Elpased Time : " << elapsed_time << "ms"<< endl;
#else
#define debug(x)
#define startTimer
#define endTimer
#endif
#define ordered_set tree<int, null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
// void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
const int mod = 1e9 + 7;

int n, s;
int dist[801][801];
char grid[801][801];
int mx, my;
int ex, ey;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool checker(int k) {
    if (dist[mx][my]<=k) return false;
    vector<vector<int> >distance(n, vector<int>(n, INT_MAX));
    queue<ai(2)>q;
    distance[mx][my] = 0;
    q.push({mx, my});
    while (q.size()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            if (x+dx[i] < 0 || x+dx[i] >= n || y+dy[i] < 0 || y+dy[i] >= n 
                || grid[x+dx[i]][y+dy[i]] == 'T') continue;
            if (((distance[x][y] +1)  / s) + k < (dist[x+dx[i]][y+dy[i]]) 
                && distance[x+dx[i]][y+dy[i]] > distance[x][y] + 1) {
                distance[x+dx[i]][y+dy[i]] =distance[x][y] + 1;
                q.push({x+dx[i], y+dy[i]});
            }
            // if (grid[x+dx[i]][y+dy[i]]=='D' &&
            //     ((distance[x][y] +1)  / s) + k < (dist[x+dx[i]][y+dy[i]]) 
            //     && distance[x+dx[i]][y+dy[i]] > distance[x][y] + 1) {
            //     distance[x+dx[i]][y+dy[i]] =distance[x][y] + 1;
            //     q.push({x+dx[i], y+dy[i]});
            // }
        }
    }
    return distance[ex][ey] !=INT_MAX;
};

void solve() {

    cin >> n >> s;
    queue<ai(2)>q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
            dist[i][j] =INT_MAX;
            if (grid[i][j] == 'M') { mx = i; my = j; }
            else if (grid[i][j] == 'D') { ex = i; ey = j; }
            else if (grid[i][j] == 'H') {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }

    while (q.size()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 4; i++) {
            if (x+dx[i] < 0 || x+dx[i] >= n || y+dy[i] < 0 || y+dy[i] >= n || grid[x+dx[i]][y+dy[i]] == 'T') continue;
            if (dist[x+dx[i]][y+dy[i]] > dist[x][y] + 1) {
                dist[x+dx[i]][y+dy[i]] = dist[x][y] + 1;
                q.push({x+dx[i], y+dy[i]});
            }
        }
    }

    int l = 0, r = 1e9, ans = -1;
    while (l <= r) {
        int mid = l + ((r - l) / 2);
        if (checker(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << endl;

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("atlarge.in","r",stdin);
    // freopen ("atlarge.out","w",stdout);
    startTimer
    int tt=1;
    // cin>>tt; // No. of testcases
    while(tt--){
        solve();
    }
    endTimer
    return 0;
}

• Subtask 1: 84 / 100