oj.uz

Submission #571363

# Submission time Handle Problem Language Result Execution time Memory
571363 2022-06-02T02:42:46 Z f4t4nt Mecho (IOI09_mecho) C++11
34 / 100
 261 ms 16292 KB 
#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] * s <= mid * s + d) 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;
}

Subtask #1
34.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 201 ms 16164 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Correct 1 ms 340 KB Output is correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Correct 1 ms 340 KB Output is correct
30 Incorrect 1 ms 340 KB Output isn't correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 16 ms 3344 KB Output is correct
34 Incorrect 11 ms 3276 KB Output isn't correct
35 Incorrect 13 ms 3276 KB Output isn't correct
36 Correct 19 ms 4264 KB Output is correct
37 Incorrect 14 ms 4156 KB Output isn't correct
38 Incorrect 16 ms 4280 KB Output isn't correct
39 Correct 25 ms 5320 KB Output is correct
40 Correct 24 ms 5268 KB Output is correct
41 Correct 62 ms 5328 KB Output is correct
42 Correct 33 ms 6520 KB Output is correct
43 Incorrect 28 ms 6420 KB Output isn't correct
44 Correct 80 ms 6496 KB Output is correct
45 Correct 38 ms 7804 KB Output is correct
46 Incorrect 27 ms 7692 KB Output isn't correct
47 Incorrect 33 ms 7700 KB Output isn't correct
48 Correct 48 ms 9240 KB Output is correct
49 Correct 49 ms 9228 KB Output is correct
50 Incorrect 44 ms 9160 KB Output isn't correct
51 Correct 55 ms 10700 KB Output is correct
52 Incorrect 38 ms 10700 KB Output isn't correct
53 Correct 139 ms 10880 KB Output is correct
54 Correct 65 ms 12512 KB Output is correct
55 Correct 69 ms 12480 KB Output is correct
56 Incorrect 58 ms 12364 KB Output isn't correct
57 Correct 76 ms 14244 KB Output is correct
58 Correct 78 ms 14300 KB Output is correct
59 Incorrect 62 ms 14176 KB Output isn't correct
60 Correct 103 ms 16152 KB Output is correct
61 Incorrect 62 ms 16012 KB Output isn't correct
62 Correct 248 ms 16160 KB Output is correct
63 Correct 207 ms 16148 KB Output is correct
64 Incorrect 83 ms 15948 KB Output isn't correct
65 Correct 261 ms 16140 KB Output is correct
66 Correct 222 ms 16072 KB Output is correct
67 Correct 76 ms 16024 KB Output is correct
68 Correct 136 ms 16236 KB Output is correct
69 Incorrect 74 ms 16020 KB Output isn't correct
70 Correct 145 ms 16188 KB Output is correct
71 Incorrect 69 ms 16016 KB Output isn't correct
72 Incorrect 71 ms 16068 KB Output isn't correct
73 Incorrect 129 ms 16172 KB Output isn't correct
74 Correct 182 ms 16292 KB Output is correct
75 Incorrect 77 ms 16064 KB Output isn't correct
76 Correct 150 ms 16168 KB Output is correct
77 Correct 177 ms 16148 KB Output is correct
78 Correct 74 ms 16032 KB Output is correct
79 Incorrect 85 ms 15996 KB Output isn't correct
80 Incorrect 72 ms 16044 KB Output isn't correct
81 Correct 167 ms 16188 KB Output is correct
82 Correct 148 ms 16128 KB Output is correct
83 Incorrect 79 ms 16076 KB Output isn't correct
84 Correct 199 ms 16228 KB Output is correct
85 Correct 197 ms 16172 KB Output is correct
86 Incorrect 73 ms 16048 KB Output isn't correct
87 Correct 186 ms 16204 KB Output is correct
88 Correct 212 ms 16124 KB Output is correct
89 Incorrect 88 ms 16076 KB Output isn't correct
90 Correct 208 ms 16200 KB Output is correct
91 Incorrect 85 ms 16076 KB Output isn't correct
92 Incorrect 79 ms 16032 KB Output isn't correct