oj.uz

Submission #965431

# Submission time Handle Problem Language Result Execution time Memory
965431 2024-04-18T14:02:58 Z Alihan_8 Mecho (IOI09_mecho) C++17
59 / 100
 640 ms 16736 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e9;

int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    vector <string> a(n);
    for ( auto &u: a ) cin >> u;
    ar <int,2> s, e;
    vector <vector<int>> bee(n, vector <int> (n, inf));
    queue <ar<int,2>> q;
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( a[i][j] == 'M' ){
                s = {i, j};
            }
            if ( a[i][j] == 'D' ){
                e = {i, j};
            }
            if ( a[i][j] == 'H' ){
                q.push({i, j});
                bee[i][j] = 0;
            }
        }
    }
    auto ok = [&](int u, int v){
        return u >= 0 && v >= 0 && u < n && v < n;
    };
    while ( !q.empty() ){
        auto [u, v] = q.front();
        q.pop();
        for ( int i = 0; i < 4; i++ ){
            int x = dx[i] + u, y = dy[i] + v;
            if ( ok(x, y) && a[x][y] != 'T' && a[x][y] != 'D' ){
                if ( chmin(bee[x][y], bee[u][v] + 1) ){
                    q.push({x, y});
                }
            }
        }
    }
    auto valid = [&](int t){
        if ( bee[s[0]][s[1]] <= t ){
            return false;
        }
        vector <vector<ar<int,2>>> dp(n, vector <ar<int,2>> (n, {inf, inf}));
        dp[s[0]][s[1]] = {t + 1, -k};
        priority_queue <ar<int,4>> q;
        q.push({-(t + 1), k, s[0], s[1]});
        while ( !q.empty() ){
            auto [val, r, u, v] = q.top();
            q.pop(); val *= -1;
            if ( dp[u][v] != ar<int,2>{val, -r} ){
                continue;
            }
            for ( int i = 0; i < 4; i++ ){
                int x = dx[i] + u, y = dy[i] + v;
                if ( !ok(x, y) || a[x][y] == 'T' ){
                    continue;
                }
                if ( r == 0 ){
                    if ( chmin(dp[x][y], ar<int,2>{val + 1, -k}) ){
                        q.push({-dp[x][y][0], k, x, y});
                    }
                } else{
                    if ( bee[x][y] > val - (r != 1) ){
                        if ( chmin(dp[x][y], ar<int,2>{val, -(r - 1)}) ){
                            q.push({-dp[x][y][0], r - 1, x, y});
                        }
                    }
                }
            }
        }
        return dp[e[0]][e[1]][0] != inf;
    };
    int l = 0, r = inf;
    while ( l + 1 < r ){
        int md = (l + r) >> 1;
        if ( valid(md) ){
            l = md;
        } else r = md;
    }
    cout << (valid(l) ? l : -1);

    cout << '\n';
}

Subtask #1
59.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 412 ms 16328 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 11 ms 3544 KB Output is correct
34 Correct 11 ms 3420 KB Output is correct
35 Correct 92 ms 3512 KB Output is correct
36 Correct 12 ms 4472 KB Output is correct
37 Correct 12 ms 4440 KB Output is correct
38 Correct 126 ms 4448 KB Output is correct
39 Correct 16 ms 5512 KB Output is correct
40 Correct 14 ms 5492 KB Output is correct
41 Correct 165 ms 5496 KB Output is correct
42 Correct 14 ms 6672 KB Output is correct
43 Correct 12 ms 6672 KB Output is correct
44 Correct 210 ms 6668 KB Output is correct
45 Correct 22 ms 7948 KB Output is correct
46 Correct 26 ms 8040 KB Output is correct
47 Correct 280 ms 8112 KB Output is correct
48 Correct 35 ms 9476 KB Output is correct
49 Correct 36 ms 9396 KB Output is correct
50 Correct 356 ms 9388 KB Output is correct
51 Correct 38 ms 11188 KB Output is correct
52 Correct 40 ms 11004 KB Output is correct
53 Correct 381 ms 10900 KB Output is correct
54 Correct 53 ms 12680 KB Output is correct
55 Correct 58 ms 12808 KB Output is correct
56 Correct 469 ms 12604 KB Output is correct
57 Correct 44 ms 14460 KB Output is correct
58 Correct 38 ms 14428 KB Output is correct
59 Correct 539 ms 14528 KB Output is correct
60 Correct 47 ms 16376 KB Output is correct
61 Correct 59 ms 16364 KB Output is correct
62 Correct 640 ms 16308 KB Output is correct
63 Incorrect 445 ms 16364 KB Output isn't correct
64 Correct 545 ms 16308 KB Output is correct
65 Incorrect 520 ms 16256 KB Output isn't correct
66 Incorrect 451 ms 16492 KB Output isn't correct
67 Incorrect 485 ms 16284 KB Output isn't correct
68 Incorrect 113 ms 16600 KB Output isn't correct
69 Correct 112 ms 16328 KB Output is correct
70 Incorrect 71 ms 16344 KB Output isn't correct
71 Incorrect 83 ms 16276 KB Output isn't correct
72 Correct 45 ms 16448 KB Output is correct
73 Correct 93 ms 16220 KB Output is correct
74 Correct 238 ms 16316 KB Output is correct
75 Incorrect 283 ms 16600 KB Output isn't correct
76 Incorrect 242 ms 16324 KB Output isn't correct
77 Incorrect 259 ms 16464 KB Output isn't correct
78 Incorrect 366 ms 16312 KB Output isn't correct
79 Correct 212 ms 16320 KB Output is correct
80 Incorrect 267 ms 16736 KB Output isn't correct
81 Incorrect 322 ms 16600 KB Output isn't correct
82 Incorrect 232 ms 16344 KB Output isn't correct
83 Incorrect 308 ms 16320 KB Output isn't correct
84 Correct 299 ms 16328 KB Output is correct
85 Incorrect 328 ms 16588 KB Output isn't correct
86 Incorrect 343 ms 16492 KB Output isn't correct
87 Correct 348 ms 16468 KB Output is correct
88 Incorrect 363 ms 16324 KB Output isn't correct
89 Correct 372 ms 16328 KB Output is correct
90 Correct 423 ms 16496 KB Output is correct
91 Correct 362 ms 16336 KB Output is correct
92 Incorrect 374 ms 16472 KB Output isn't correct