oj.uz

Submission #892634

# Submission time Handle Problem Language Result Execution time Memory
892634 2023-12-25T15:44:42 Z seriouslyFlawed Mecho (IOI09_mecho) C++17
9 / 100
 238 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

// Shortcuts for common operations
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define endl "\n"

// Type definitions for convenience
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef unordered_set<int> usi;
typedef unordered_map<int, int> umii;

// Debugging macros
#define debug(x) cerr << #x << " = " << (x) << '\n'
#define debug_vector(v) _debug_vector(#v, v)
template<typename T>
void _debug_vector(const string& name, const vector<T>& a) {
    cerr << name << " = [ ";
    for(const auto &x : a) cerr << x << ' ';
    cerr << "]\n";
}

// I/O redirection for local testing
#define iofile(io) \
        freopen((io + ".in").c_str(), "r", stdin); \
        freopen((io + ".out").c_str(), "w", stdout);

// delta for floodfill
vi dx = {0, 1, 0, -1};
vi dy = {1, 0, -1, 0};

// extended deltas for floodfill
vi edx = {0, 1, 0, -1, 1, 1, -1, -1};
vi edy = {1, 0, -1, 0, 1, -1, 1, -1};

// Common outputs
void yes() { cout << "YES" << '\n'; }
void no() { cout << "NO" << '\n'; }

// cin.tie(0)->sync_with_stdio(0);

void fx() {
    // Functionality for fx
    int n, k;
    cin >> n >> k;

    vector<string>tab(n);
    vvi bee(n, vi(n, INT_MAX));
    vii hives;
    pii start;

    for(int i = 0; i < n; i++){
        cin >> tab[i];
        for(int j = 0; j < n; j++){
            if(tab[i][j] == 'M') start = {i, j};
            else if(tab[i][j] == 'H') hives.pb({i, j});
        }
    }

    queue<pair<int, pii>>q;
    for(auto &hive: hives){
        q.push({0, hive});
        bee[hive.f][hive.s] = 0;
    }

    while(!q.empty()){
        auto &[t, hive] = q.front();
        q.pop();
        auto &[x, y] = hive;
        
        for(int i = 0; i < 4; i++){
            auto [X, Y] = make_pair(x+dx[i], y+dy[i]);
            if(X >= 0 and X < n and Y >= 0 and Y < n and (tab[X][Y] == 'G' or tab[X][Y] == 'M') and bee[X][Y] > t + 1){
                q.push({t+1, {X, Y}});
                bee[X][Y] = t+1;
            }
        }
    }

    queue<pair<array<int, 3>, pii>>que;
    vector<vi>best(n, vi(n, INT_MIN)); // <- see init.
    que.push({{0, bee[start.f][start.s], k}, {start.f, start.s}}); //<- sure about init?
    best[start.f][start.s] = bee[start.f][start.s];
    int res = INT_MIN;

    while(!que.empty()){
        auto [T, C] = que.front();
        que.pop();
        auto [t, s, steps] = T;
        auto [x, y] = C;

        if(tab[x][y] == 'D') res = max(res, best[x][y]);
        
        for(int i = 0; i < 4; i++){
            auto [X, Y] = make_pair(x + dx[i], y + dy[i]);

            if(X >= 0 and X < n and Y >= 0 and Y < n and tab[X][Y] != 'T' and (bee[X][Y] > (steps?t:t+1)) and best[X][Y] <= min(s, bee[X][Y] - (steps?t:t+1))){
                que.push({{(steps?t:t+1), min(s, bee[X][Y] - (steps?t:t+1)), (steps?steps-1:k-1)}, {X, Y}});
                best[X][Y] = max(best[X][Y], min(s, bee[X][Y] -(steps?t:t+1)));
            }
        }
    }

    cout << ((res <= 0)?-1:res-1) << endl;
}

int main() {
    // Uncomment the following lines for file I/O
    // iofile(string("hello"));
    
    // Uncomment the following lines for multiple test cases
    // int t; cin >> t;
    // while(t--) fx();
    
    // Single test case
    fx();
    
    return 0;
}

Subtask #1
9.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Runtime error 145 ms 65536 KB Execution killed with signal 9
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 115 ms 65536 KB Execution killed with signal 9
8 Incorrect 0 ms 348 KB Output isn't correct
9 Runtime error 114 ms 65536 KB Execution killed with signal 9
10 Correct 0 ms 348 KB Output is correct
11 Correct 134 ms 32056 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Runtime error 91 ms 65536 KB Execution killed with signal 9
14 Runtime error 116 ms 65536 KB Execution killed with signal 9
15 Incorrect 0 ms 344 KB Output isn't correct
16 Runtime error 131 ms 65536 KB Execution killed with signal 9
17 Incorrect 0 ms 344 KB Output isn't correct
18 Runtime error 132 ms 65536 KB Execution killed with signal 9
19 Incorrect 0 ms 348 KB Output isn't correct
20 Runtime error 130 ms 65536 KB Execution killed with signal 9
21 Incorrect 1 ms 348 KB Output isn't correct
22 Runtime error 133 ms 65536 KB Execution killed with signal 9
23 Incorrect 0 ms 348 KB Output isn't correct
24 Runtime error 127 ms 65536 KB Execution killed with signal 9
25 Incorrect 1 ms 348 KB Output isn't correct
26 Runtime error 135 ms 65536 KB Execution killed with signal 9
27 Incorrect 0 ms 344 KB Output isn't correct
28 Runtime error 130 ms 65536 KB Execution killed with signal 9
29 Incorrect 0 ms 348 KB Output isn't correct
30 Runtime error 128 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 600 KB Output isn't correct
32 Runtime error 125 ms 65536 KB Execution killed with signal 9
33 Incorrect 4 ms 1372 KB Output isn't correct
34 Runtime error 129 ms 65536 KB Execution killed with signal 9
35 Runtime error 146 ms 65536 KB Execution killed with signal 9
36 Incorrect 5 ms 1884 KB Output isn't correct
37 Runtime error 132 ms 65536 KB Execution killed with signal 9
38 Runtime error 120 ms 65536 KB Execution killed with signal 9
39 Incorrect 6 ms 2140 KB Output isn't correct
40 Runtime error 128 ms 65536 KB Execution killed with signal 9
41 Runtime error 119 ms 65536 KB Execution killed with signal 9
42 Incorrect 8 ms 2908 KB Output isn't correct
43 Runtime error 128 ms 65536 KB Execution killed with signal 9
44 Runtime error 122 ms 65536 KB Execution killed with signal 9
45 Incorrect 10 ms 3164 KB Output isn't correct
46 Runtime error 136 ms 65536 KB Execution killed with signal 9
47 Runtime error 121 ms 65536 KB Execution killed with signal 9
48 Incorrect 11 ms 3676 KB Output isn't correct
49 Runtime error 131 ms 65536 KB Execution killed with signal 9
50 Runtime error 126 ms 65536 KB Execution killed with signal 9
51 Incorrect 17 ms 4184 KB Output isn't correct
52 Runtime error 128 ms 65536 KB Execution killed with signal 9
53 Runtime error 125 ms 65536 KB Execution killed with signal 9
54 Incorrect 15 ms 4956 KB Output isn't correct
55 Runtime error 131 ms 65536 KB Execution killed with signal 9
56 Runtime error 146 ms 65536 KB Execution killed with signal 9
57 Incorrect 17 ms 5464 KB Output isn't correct
58 Runtime error 132 ms 65536 KB Execution killed with signal 9
59 Runtime error 132 ms 65536 KB Execution killed with signal 9
60 Incorrect 20 ms 6232 KB Output isn't correct
61 Runtime error 160 ms 65536 KB Execution killed with signal 9
62 Runtime error 161 ms 65536 KB Execution killed with signal 9
63 Runtime error 238 ms 65536 KB Execution killed with signal 9
64 Runtime error 166 ms 65536 KB Execution killed with signal 9
65 Runtime error 138 ms 65536 KB Execution killed with signal 9
66 Runtime error 144 ms 65536 KB Execution killed with signal 9
67 Runtime error 235 ms 65536 KB Execution killed with signal 9
68 Runtime error 130 ms 65536 KB Execution killed with signal 9
69 Runtime error 130 ms 65536 KB Execution killed with signal 9
70 Runtime error 141 ms 65536 KB Execution killed with signal 9
71 Runtime error 129 ms 65536 KB Execution killed with signal 9
72 Runtime error 138 ms 65536 KB Execution killed with signal 9
73 Runtime error 105 ms 65536 KB Execution killed with signal 9
74 Runtime error 115 ms 65536 KB Execution killed with signal 9
75 Runtime error 134 ms 65536 KB Execution killed with signal 9
76 Runtime error 128 ms 65536 KB Execution killed with signal 9
77 Runtime error 114 ms 65536 KB Execution killed with signal 9
78 Runtime error 114 ms 65536 KB Execution killed with signal 9
79 Runtime error 109 ms 65536 KB Execution killed with signal 9
80 Runtime error 117 ms 65536 KB Execution killed with signal 9
81 Runtime error 109 ms 65536 KB Execution killed with signal 9
82 Runtime error 109 ms 65536 KB Execution killed with signal 9
83 Runtime error 126 ms 65536 KB Execution killed with signal 9
84 Runtime error 127 ms 65536 KB Execution killed with signal 9
85 Runtime error 159 ms 65536 KB Execution killed with signal 9
86 Runtime error 156 ms 65536 KB Execution killed with signal 9
87 Runtime error 125 ms 65536 KB Execution killed with signal 9
88 Runtime error 157 ms 65536 KB Execution killed with signal 9
89 Runtime error 150 ms 65536 KB Execution killed with signal 9
90 Runtime error 145 ms 65536 KB Execution killed with signal 9
91 Runtime error 147 ms 65536 KB Execution killed with signal 9
92 Runtime error 148 ms 65536 KB Execution killed with signal 9