oj.uz

Submission #892719

# Submission time Handle Problem Language Result Execution time Memory
892719 2023-12-25T18:02:01 Z seriouslyFlawed Mecho (IOI09_mecho) C++17
17 / 100
 1000 ms 11372 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);
vvi bee;
vector<string>tab;
int n, k;
pii start;
int best[801][801];

bool isViable(int target){
    if(bee[start.f][start.s] <= target) return false;

    memset(best, -1, sizeof best);
    queue<pair<pii, pii>>q;
    q.push({{target, k}, start});
    best[start.f][start.s] = bee[start.f][start.s] - target;

    while(!q.empty()){
        auto &[T, curr] = q.front();
        auto &[t, steps] = T;
        q.pop();

        if(tab[curr.f][curr.s] == 'D') return (best[curr.f][curr.s] > 0);

        for(int i = 0; i < 4; i++){
            auto [x, y] = make_pair(curr.f + dx[i], curr.s + 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(best[curr.f][curr.s], bee[x][y] - (steps?t:t+1))){
                best[x][y] = min(best[curr.f][curr.s], bee[x][y] - (steps?t:t+1));
                q.push({{(steps)?t:t+1, (steps?steps-1:k-1)}, {x, y}});
            }
        }
    }

    return false;

}

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

    tab.assign(n, "");
    bee.assign(n, vi(n, INT_MAX));
    vii hives;

    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' or tab[X][Y] == 'D') and bee[X][Y] > t + 1){
                q.push({t+1, {X, Y}});
                bee[X][Y] = t+1;
            }
        }
    }

    if(!isViable(0)){
        cout << "-1" << endl;
        return;
    }

    int lo = 0;
    int hi = 805;
    while(hi > lo){
        int mid = (lo + hi +1)/2;
        if(isViable(mid)) lo = mid;
        else hi = mid-1; 
    }

    cout << lo << endl;
}

int main() {
    // Uncomment the following lines for file I/O
    // iofile(string("hello"))
    cin.tie(0)->sync_with_stdio(0);

    
    // Uncomment the following lines for multiple test cases
    // int t; cin >> t;
    // while(t--) fx();
    
    // Single test case
    fx();
    
    return 0;
}

Subtask #1
17.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2904 KB Output isn't correct
2 Incorrect 1 ms 2908 KB Output isn't correct
3 Incorrect 1 ms 2908 KB Output isn't correct
4 Incorrect 1 ms 2908 KB Output isn't correct
5 Correct 1 ms 2908 KB Output is correct
6 Incorrect 1 ms 2916 KB Output isn't correct
7 Incorrect 126 ms 6176 KB Output isn't correct
8 Incorrect 1 ms 2904 KB Output isn't correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 1 ms 2908 KB Output is correct
12 Incorrect 1 ms 2908 KB Output isn't correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 1 ms 2908 KB Output is correct
15 Incorrect 1 ms 2908 KB Output isn't correct
16 Correct 1 ms 2908 KB Output is correct
17 Incorrect 1 ms 2908 KB Output isn't correct
18 Correct 1 ms 2908 KB Output is correct
19 Incorrect 1 ms 2908 KB Output isn't correct
20 Correct 1 ms 2908 KB Output is correct
21 Incorrect 1 ms 2908 KB Output isn't correct
22 Correct 1 ms 2908 KB Output is correct
23 Incorrect 1 ms 2904 KB Output isn't correct
24 Correct 2 ms 2908 KB Output is correct
25 Incorrect 1 ms 2908 KB Output isn't correct
26 Incorrect 2 ms 2908 KB Output isn't correct
27 Incorrect 1 ms 2908 KB Output isn't correct
28 Incorrect 1 ms 2908 KB Output isn't correct
29 Incorrect 1 ms 2908 KB Output isn't correct
30 Incorrect 1 ms 2908 KB Output isn't correct
31 Incorrect 2 ms 2908 KB Output isn't correct
32 Incorrect 1 ms 2908 KB Output isn't correct
33 Incorrect 3 ms 3420 KB Output isn't correct
34 Incorrect 3 ms 3420 KB Output isn't correct
35 Correct 715 ms 3756 KB Output is correct
36 Incorrect 3 ms 3676 KB Output isn't correct
37 Incorrect 3 ms 3676 KB Output isn't correct
38 Execution timed out 1033 ms 4200 KB Time limit exceeded
39 Incorrect 4 ms 3944 KB Output isn't correct
40 Incorrect 4 ms 3932 KB Output isn't correct
41 Execution timed out 1064 ms 4208 KB Time limit exceeded
42 Incorrect 4 ms 4184 KB Output isn't correct
43 Incorrect 4 ms 4184 KB Output isn't correct
44 Runtime error 153 ms 8512 KB Execution killed with signal 11
45 Incorrect 5 ms 4444 KB Output isn't correct
46 Incorrect 5 ms 4324 KB Output isn't correct
47 Execution timed out 1018 ms 4960 KB Time limit exceeded
48 Incorrect 5 ms 4696 KB Output isn't correct
49 Incorrect 6 ms 4700 KB Output isn't correct
50 Runtime error 333 ms 10016 KB Execution killed with signal 11
51 Incorrect 6 ms 4952 KB Output isn't correct
52 Incorrect 7 ms 4956 KB Output isn't correct
53 Execution timed out 1008 ms 10520 KB Time limit exceeded
54 Incorrect 7 ms 5212 KB Output isn't correct
55 Incorrect 8 ms 5252 KB Output isn't correct
56 Runtime error 649 ms 11372 KB Execution killed with signal 11
57 Incorrect 8 ms 5720 KB Output isn't correct
58 Incorrect 9 ms 5720 KB Output isn't correct
59 Execution timed out 1037 ms 6480 KB Time limit exceeded
60 Incorrect 13 ms 5976 KB Output isn't correct
61 Incorrect 9 ms 5976 KB Output isn't correct
62 Execution timed out 1095 ms 6844 KB Time limit exceeded
63 Incorrect 21 ms 5976 KB Output isn't correct
64 Incorrect 121 ms 5980 KB Output isn't correct
65 Incorrect 115 ms 6212 KB Output isn't correct
66 Incorrect 92 ms 5980 KB Output isn't correct
67 Correct 23 ms 5968 KB Output is correct
68 Correct 37 ms 6236 KB Output is correct
69 Correct 41 ms 5976 KB Output is correct
70 Correct 31 ms 6232 KB Output is correct
71 Correct 28 ms 6236 KB Output is correct
72 Correct 21 ms 6236 KB Output is correct
73 Correct 33 ms 6448 KB Output is correct
74 Incorrect 177 ms 6620 KB Output isn't correct
75 Correct 267 ms 6624 KB Output is correct
76 Correct 275 ms 6492 KB Output is correct
77 Correct 269 ms 6444 KB Output is correct
78 Correct 28 ms 6492 KB Output is correct
79 Incorrect 76 ms 6564 KB Output isn't correct
80 Incorrect 63 ms 6492 KB Output isn't correct
81 Correct 95 ms 6572 KB Output is correct
82 Incorrect 64 ms 6392 KB Output isn't correct
83 Correct 103 ms 6744 KB Output is correct
84 Correct 202 ms 6740 KB Output is correct
85 Correct 954 ms 6508 KB Output is correct
86 Execution timed out 1044 ms 6492 KB Time limit exceeded
87 Correct 174 ms 6480 KB Output is correct
88 Correct 589 ms 6440 KB Output is correct
89 Execution timed out 1058 ms 6736 KB Time limit exceeded
90 Correct 127 ms 6428 KB Output is correct
91 Correct 189 ms 6432 KB Output is correct
92 Correct 131 ms 6436 KB Output is correct