oj.uz

Submission #571025

# Submission time Handle Problem Language Result Execution time Memory
571025 2022-06-01T05:20:18 Z f4t4nt Mecho (IOI09_mecho) C++11
17 / 100
 265 ms 16332 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
17.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 214 ms 16208 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Correct 0 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 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Correct 1 ms 340 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Correct 1 ms 340 KB Output is correct
25 Incorrect 1 ms 340 KB Output isn't correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Incorrect 1 ms 340 KB Output isn't correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Incorrect 1 ms 340 KB Output isn't correct
31 Incorrect 1 ms 340 KB Output isn't correct
32 Correct 1 ms 340 KB Output is correct
33 Incorrect 14 ms 3348 KB Output isn't correct
34 Incorrect 12 ms 3284 KB Output isn't correct
35 Incorrect 13 ms 3280 KB Output isn't correct
36 Incorrect 21 ms 4324 KB Output isn't correct
37 Incorrect 15 ms 4152 KB Output isn't correct
38 Incorrect 20 ms 4156 KB Output isn't correct
39 Incorrect 26 ms 5332 KB Output isn't correct
40 Correct 27 ms 5256 KB Output is correct
41 Correct 69 ms 5324 KB Output is correct
42 Incorrect 34 ms 6636 KB Output isn't correct
43 Incorrect 25 ms 6484 KB Output isn't correct
44 Correct 78 ms 6504 KB Output is correct
45 Incorrect 38 ms 7816 KB Output isn't correct
46 Incorrect 28 ms 7696 KB Output isn't correct
47 Incorrect 36 ms 7772 KB Output isn't correct
48 Incorrect 49 ms 9424 KB Output isn't correct
49 Correct 50 ms 9228 KB Output is correct
50 Incorrect 42 ms 9164 KB Output isn't correct
51 Incorrect 58 ms 10856 KB Output isn't correct
52 Incorrect 39 ms 10600 KB Output isn't correct
53 Correct 156 ms 10700 KB Output is correct
54 Incorrect 66 ms 12488 KB Output isn't correct
55 Correct 68 ms 12520 KB Output is correct
56 Incorrect 57 ms 12372 KB Output isn't correct
57 Incorrect 86 ms 14256 KB Output isn't correct
58 Correct 86 ms 14320 KB Output is correct
59 Incorrect 64 ms 14100 KB Output isn't correct
60 Incorrect 91 ms 16196 KB Output isn't correct
61 Incorrect 62 ms 16008 KB Output isn't correct
62 Correct 251 ms 16196 KB Output is correct
63 Correct 227 ms 16128 KB Output is correct
64 Incorrect 88 ms 15948 KB Output isn't correct
65 Correct 265 ms 16168 KB Output is correct
66 Incorrect 224 ms 16032 KB Output isn't correct
67 Correct 76 ms 16028 KB Output is correct
68 Correct 148 ms 16236 KB Output is correct
69 Incorrect 77 ms 16024 KB Output isn't correct
70 Correct 133 ms 16244 KB Output is correct
71 Incorrect 67 ms 16024 KB Output isn't correct
72 Incorrect 81 ms 16032 KB Output isn't correct
73 Incorrect 116 ms 16180 KB Output isn't correct
74 Correct 167 ms 16184 KB Output is correct
75 Incorrect 81 ms 16168 KB Output isn't correct
76 Correct 152 ms 16176 KB Output is correct
77 Correct 178 ms 16156 KB Output is correct
78 Correct 78 ms 16040 KB Output is correct
79 Incorrect 86 ms 16076 KB Output isn't correct
80 Incorrect 73 ms 16044 KB Output isn't correct
81 Correct 178 ms 16252 KB Output is correct
82 Correct 159 ms 16184 KB Output is correct
83 Incorrect 76 ms 16044 KB Output isn't correct
84 Correct 195 ms 16172 KB Output is correct
85 Correct 190 ms 16156 KB Output is correct
86 Incorrect 75 ms 16032 KB Output isn't correct
87 Correct 200 ms 16168 KB Output is correct
88 Correct 189 ms 16332 KB Output is correct
89 Incorrect 94 ms 16104 KB Output isn't correct
90 Correct 218 ms 16156 KB Output is correct
91 Incorrect 82 ms 16076 KB Output isn't correct
92 Incorrect 74 ms 16140 KB Output isn't correct