oj.uz

Submission #446606

# Submission time Handle Problem Language Result Execution time Memory
446606 2021-07-22T16:58:16 Z JerryLiu06 Mecho (IOI09_mecho) C++17
39 / 100
 229 ms 6368 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MX = 810;
const ll INF = 1e18;

const int DIR[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

int N, S; char G[MX][MX]; int SX, SY, EX, EY;

int distToHive[MX][MX], distToStart[MX][MX];

bool valid(int X, int Y) { return X >= 1 && X <= N && Y >= 1 && Y <= N; }

bool valid(int tim) {
    memset(distToStart, -1, sizeof distToStart);

    distToStart[SX][SY] = 0; 

    queue<pi> Q; Q.push({SX, SY});

    while (!Q.empty()) {
        pi cur = Q.front(); Q.pop();

        if (cur.f == EX && cur.s == EY) return true;

        F0R(i, 4) {
            int nx = cur.f + DIR[i][0];
            int ny = cur.s + DIR[i][1];

            if (!valid(nx, ny)) continue;

            if (G[nx][ny] != 'T' && distToStart[nx][ny] == -1) {
                distToStart[nx][ny] = distToStart[cur.f][cur.s] + 1;

                if (distToHive[nx][ny] != -1 && distToStart[nx][ny] / S + tim >= distToHive[nx][ny]) {
                    continue;
                }
                Q.push({nx, ny});
            }
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> S; queue<pi> Q; memset(distToHive, -1, sizeof distToHive);
    
    FOR(i, 1, N + 1) FOR(j, 1, N + 1) {
        char C; cin >> C; if (C == 'M') { SX = i, SY = j; } if (C == 'D') { EX = i, EY = j; }

        if (C == 'H') { Q.push({i, j}); distToHive[i][j] = 0; } G[i][j] = C;
    }
    while (!Q.empty()) {
        pi cur = Q.front(); Q.pop();

        F0R(i, 4) {
            int nx = cur.f + DIR[i][0];
            int ny = cur.s + DIR[i][1];

            if (!valid(nx, ny)) continue; 

            if (distToHive[nx][ny] == -1 && G[nx][ny] != 'T' && G[nx][ny] != 'D') {
                distToHive[nx][ny] = distToHive[cur.f][cur.s] + 1;
                
                Q.push({nx, ny});
            }
        }
    }
    int low = 0; int high = N; int res = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (valid(mid)) {
            low = mid + 1; res = mid;
        }
        else {
            high = mid - 1;
        }
    }
    cout << res;
}

Subtask #1
39.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5456 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 3 ms 5452 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 100 ms 6096 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 3 ms 5452 KB Output is correct
10 Correct 3 ms 5452 KB Output is correct
11 Correct 3 ms 5452 KB Output is correct
12 Incorrect 4 ms 5452 KB Output isn't correct
13 Incorrect 4 ms 5452 KB Output isn't correct
14 Correct 4 ms 5452 KB Output is correct
15 Incorrect 3 ms 5452 KB Output isn't correct
16 Incorrect 4 ms 5452 KB Output isn't correct
17 Incorrect 3 ms 5452 KB Output isn't correct
18 Incorrect 3 ms 5452 KB Output isn't correct
19 Incorrect 3 ms 5452 KB Output isn't correct
20 Incorrect 3 ms 5452 KB Output isn't correct
21 Incorrect 4 ms 5452 KB Output isn't correct
22 Incorrect 3 ms 5452 KB Output isn't correct
23 Incorrect 3 ms 5452 KB Output isn't correct
24 Incorrect 3 ms 5452 KB Output isn't correct
25 Incorrect 3 ms 5452 KB Output isn't correct
26 Incorrect 4 ms 5452 KB Output isn't correct
27 Incorrect 3 ms 5452 KB Output isn't correct
28 Incorrect 3 ms 5452 KB Output isn't correct
29 Incorrect 3 ms 5452 KB Output isn't correct
30 Incorrect 3 ms 5452 KB Output isn't correct
31 Incorrect 3 ms 5452 KB Output isn't correct
32 Incorrect 4 ms 5452 KB Output isn't correct
33 Incorrect 9 ms 5732 KB Output isn't correct
34 Incorrect 8 ms 5708 KB Output isn't correct
35 Correct 25 ms 5708 KB Output is correct
36 Incorrect 9 ms 5708 KB Output isn't correct
37 Incorrect 9 ms 5772 KB Output isn't correct
38 Correct 31 ms 5780 KB Output is correct
39 Incorrect 9 ms 5708 KB Output isn't correct
40 Incorrect 9 ms 5808 KB Output isn't correct
41 Correct 40 ms 5804 KB Output is correct
42 Incorrect 11 ms 5856 KB Output isn't correct
43 Incorrect 10 ms 5836 KB Output isn't correct
44 Correct 56 ms 5836 KB Output is correct
45 Incorrect 12 ms 5864 KB Output isn't correct
46 Incorrect 12 ms 5836 KB Output isn't correct
47 Correct 60 ms 5892 KB Output is correct
48 Incorrect 15 ms 5836 KB Output isn't correct
49 Incorrect 14 ms 5836 KB Output isn't correct
50 Correct 70 ms 5924 KB Output is correct
51 Incorrect 16 ms 5972 KB Output isn't correct
52 Incorrect 17 ms 5912 KB Output isn't correct
53 Correct 93 ms 5964 KB Output is correct
54 Incorrect 18 ms 6004 KB Output isn't correct
55 Incorrect 18 ms 5888 KB Output isn't correct
56 Correct 101 ms 6020 KB Output is correct
57 Incorrect 20 ms 5964 KB Output isn't correct
58 Incorrect 19 ms 5964 KB Output isn't correct
59 Correct 133 ms 5920 KB Output is correct
60 Incorrect 23 ms 5984 KB Output isn't correct
61 Incorrect 22 ms 6032 KB Output isn't correct
62 Correct 135 ms 6096 KB Output is correct
63 Correct 123 ms 6196 KB Output is correct
64 Incorrect 229 ms 6040 KB Output isn't correct
65 Correct 156 ms 6072 KB Output is correct
66 Correct 128 ms 6084 KB Output is correct
67 Correct 131 ms 6084 KB Output is correct
68 Correct 54 ms 6076 KB Output is correct
69 Correct 47 ms 6084 KB Output is correct
70 Correct 46 ms 6108 KB Output is correct
71 Correct 46 ms 6020 KB Output is correct
72 Incorrect 35 ms 6120 KB Output isn't correct
73 Incorrect 49 ms 6232 KB Output isn't correct
74 Correct 79 ms 6348 KB Output is correct
75 Correct 69 ms 6232 KB Output is correct
76 Correct 78 ms 6368 KB Output is correct
77 Correct 74 ms 6340 KB Output is correct
78 Correct 100 ms 6344 KB Output is correct
79 Correct 70 ms 6324 KB Output is correct
80 Correct 76 ms 6332 KB Output is correct
81 Correct 87 ms 6208 KB Output is correct
82 Correct 73 ms 6328 KB Output is correct
83 Correct 96 ms 6212 KB Output is correct
84 Correct 88 ms 6284 KB Output is correct
85 Correct 102 ms 6284 KB Output is correct
86 Correct 93 ms 6288 KB Output is correct
87 Correct 92 ms 6296 KB Output is correct
88 Correct 98 ms 6220 KB Output is correct
89 Correct 96 ms 6116 KB Output is correct
90 Correct 111 ms 6236 KB Output is correct
91 Correct 101 ms 6240 KB Output is correct
92 Correct 88 ms 6252 KB Output is correct