oj.uz

Submission #892712

# Submission time Handle Problem Language Result Execution time Memory
892712 2023-12-25T17:53:05 Z seriouslyFlawed Mecho (IOI09_mecho) C++17
4 / 100
 1000 ms 7700 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 < n; 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;
            }
        }
    }

    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
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2908 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 Incorrect 1 ms 2904 KB Output isn't correct
6 Incorrect 1 ms 2932 KB Output isn't correct
7 Execution timed out 1097 ms 6236 KB Time limit exceeded
8 Correct 1 ms 2908 KB Output is correct
9 Incorrect 1 ms 2908 KB Output isn't correct
10 Incorrect 1 ms 2908 KB Output isn't correct
11 Incorrect 1 ms 2908 KB Output isn't correct
12 Incorrect 1 ms 2908 KB Output isn't correct
13 Incorrect 1 ms 2904 KB Output isn't correct
14 Correct 1 ms 2908 KB Output is correct
15 Incorrect 1 ms 2908 KB Output isn't correct
16 Incorrect 1 ms 2908 KB Output isn't correct
17 Incorrect 1 ms 2908 KB Output isn't correct
18 Incorrect 1 ms 2908 KB Output isn't correct
19 Incorrect 1 ms 2904 KB Output isn't correct
20 Incorrect 1 ms 2908 KB Output isn't correct
21 Incorrect 1 ms 2908 KB Output isn't correct
22 Incorrect 1 ms 2904 KB Output isn't correct
23 Incorrect 1 ms 2908 KB Output isn't correct
24 Incorrect 1 ms 2908 KB Output isn't correct
25 Incorrect 1 ms 2908 KB Output isn't correct
26 Incorrect 1 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 1 ms 2908 KB Output isn't correct
32 Incorrect 1 ms 2908 KB Output isn't correct
33 Incorrect 2 ms 3672 KB Output isn't correct
34 Incorrect 3 ms 3420 KB Output isn't correct
35 Incorrect 49 ms 3736 KB Output isn't correct
36 Incorrect 3 ms 3672 KB Output isn't correct
37 Incorrect 3 ms 3676 KB Output isn't correct
38 Incorrect 123 ms 4200 KB Output isn't correct
39 Incorrect 3 ms 3932 KB Output isn't correct
40 Incorrect 4 ms 3932 KB Output isn't correct
41 Incorrect 211 ms 4152 KB Output isn't correct
42 Incorrect 4 ms 4188 KB Output isn't correct
43 Incorrect 5 ms 4188 KB Output isn't correct
44 Incorrect 330 ms 4828 KB Output isn't correct
45 Incorrect 4 ms 4444 KB Output isn't correct
46 Incorrect 7 ms 4300 KB Output isn't correct
47 Incorrect 481 ms 4932 KB Output isn't correct
48 Incorrect 5 ms 4616 KB Output isn't correct
49 Incorrect 10 ms 4804 KB Output isn't correct
50 Incorrect 739 ms 5200 KB Output isn't correct
51 Incorrect 6 ms 4956 KB Output isn't correct
52 Incorrect 10 ms 4956 KB Output isn't correct
53 Execution timed out 1065 ms 5716 KB Time limit exceeded
54 Incorrect 6 ms 5212 KB Output isn't correct
55 Incorrect 12 ms 5212 KB Output isn't correct
56 Execution timed out 1074 ms 6472 KB Time limit exceeded
57 Incorrect 7 ms 5724 KB Output isn't correct
58 Incorrect 15 ms 5724 KB Output isn't correct
59 Execution timed out 1088 ms 6588 KB Time limit exceeded
60 Incorrect 8 ms 5976 KB Output isn't correct
61 Incorrect 18 ms 5980 KB Output isn't correct
62 Execution timed out 1088 ms 7356 KB Time limit exceeded
63 Incorrect 21 ms 6008 KB Output isn't correct
64 Incorrect 21 ms 5980 KB Output isn't correct
65 Incorrect 21 ms 5980 KB Output isn't correct
66 Incorrect 22 ms 5980 KB Output isn't correct
67 Correct 21 ms 5976 KB Output is correct
68 Incorrect 20 ms 6236 KB Output isn't correct
69 Incorrect 21 ms 6236 KB Output isn't correct
70 Incorrect 20 ms 6236 KB Output isn't correct
71 Incorrect 21 ms 6048 KB Output isn't correct
72 Incorrect 48 ms 6232 KB Output isn't correct
73 Incorrect 885 ms 7104 KB Output isn't correct
74 Execution timed out 1033 ms 7544 KB Time limit exceeded
75 Execution timed out 1051 ms 7336 KB Time limit exceeded
76 Execution timed out 1054 ms 7700 KB Time limit exceeded
77 Execution timed out 1055 ms 7380 KB Time limit exceeded
78 Correct 710 ms 6564 KB Output is correct
79 Incorrect 713 ms 6576 KB Output isn't correct
80 Incorrect 720 ms 6572 KB Output isn't correct
81 Incorrect 692 ms 6572 KB Output isn't correct
82 Incorrect 677 ms 6568 KB Output isn't correct
83 Execution timed out 1035 ms 6488 KB Time limit exceeded
84 Execution timed out 1071 ms 6492 KB Time limit exceeded
85 Execution timed out 1060 ms 6492 KB Time limit exceeded
86 Execution timed out 1028 ms 6488 KB Time limit exceeded
87 Execution timed out 1055 ms 6492 KB Time limit exceeded
88 Execution timed out 1045 ms 6232 KB Time limit exceeded
89 Execution timed out 1045 ms 6252 KB Time limit exceeded
90 Execution timed out 1039 ms 6232 KB Time limit exceeded
91 Execution timed out 1055 ms 6232 KB Time limit exceeded
92 Execution timed out 1073 ms 6236 KB Time limit exceeded