oj.uz

Submission #581481

# Submission time Handle Problem Language Result Execution time Memory
581481 2022-06-22T16:53:42 Z Saeed_247 Mecho (IOI09_mecho) C++17
42 / 100
 1000 ms 12064 KB 
#include <bits/stdc++.h>
using namespace std;
template<typename T> void dout(string name, T arg) {
    cerr << name << " = " << arg << "\e[39m" << endl;
}
template<typename T1, typename... T2> void dout(string names, T1 arg, T2... args) {
    cerr << names.substr(0, names.find(',')) << " = " << arg << " | ";
    dout(names.substr(names.find(',') + 2), args...);
}
#define debug(...) cerr << "\e[91m" << "[" << __LINE__ << ":" << __func__ << "]=> ", dout(#__VA_ARGS__,  __VA_ARGS__);

const pair<int, int> dir[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
long long n, s;
vector<vector<char>> arr;
vector<pair<int, int>> hives;
pair<int, int> m, d;
queue<pair<int, int>> q;

bool move(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < n;
}

bool check(long long tim) {
    while (q.size()) q.pop();
    vector<vector<long long>> dist(n, vector<long long>(n, INT_MAX)), swarm(n, vector<long long>(n, INT_MAX));
    dist[m.first][m.second] = 0;
    q.push(m);
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto [xx, yy] : dir) if (move(x + xx, y + yy) && (arr[x + xx][y + yy] == 'G' || 
            arr[x + xx][y + yy] == 'D') && dist[x + xx][y + yy] > dist[x][y] + 1) {
                dist[x + xx][y + yy] = dist[x][y] + 1;
                q.push({x + xx, y + yy});
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = dist[i][j] / s + (dist[i][j] % s != 0);
            dist[i][j] += tim;
        }
    }
    for (auto [x, y] : hives) {
        swarm[x][y] = 0;
        q.push({x, y});
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto [xx, yy] : dir) if (move(x + xx, y + yy) && arr[x + xx][y + yy] == 'G' && swarm[x + xx][y + yy] > swarm[x][y] + 1) {
                swarm[x + xx][y + yy] = swarm[x][y] + 1;
                q.push({x + xx, y + yy});
        }
    }
    q.push(m);
    dist[m.first][m.second] = -1;
    while (!q.empty()) {
        auto [x, y] = q.front();
        if (q.front() == d) return true;
        q.pop();
        for (auto [xx, yy] : dir) if (move(x + xx, y + yy) && (arr[x + xx][y + yy] == 'G' || 
            arr[x + xx][y + yy] == 'D') && dist[x + xx][y + yy] != -1 && (dist[x + xx][y + yy] < swarm[x + xx][y + yy] || 
                (dist[x + xx][y + yy] == swarm[x + xx][y + yy] && dist[d.first][d.second] == dist[x + xx][y + yy]))) {
                q.push({x + xx, y + yy});
                dist[x + xx][y + yy] = -1;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    arr.resize(n, vector<char> (n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 'M') {
                m = {i, j};
            }
            if (arr[i][j] == 'H') {
                hives.push_back({i, j});
            }
            if (arr[i][j] == 'D') {
                d = {i, j};
            }
        }
    }
    long long l = 0, h = 640000;
    while (h - l > 1) {
        int mid = (h + l) / 2;
        if (check(mid)) l = mid;
        else h = mid;
    }
    cout << l << '\n';
    return 0;
}

Subtask #1
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 828 ms 11820 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 3 ms 340 KB Output isn't correct
13 Correct 4 ms 320 KB Output is correct
14 Incorrect 4 ms 340 KB Output isn't correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 324 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 3 ms 340 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 5 ms 324 KB Output is correct
32 Correct 4 ms 432 KB Output is correct
33 Correct 85 ms 2524 KB Output is correct
34 Correct 80 ms 2524 KB Output is correct
35 Incorrect 98 ms 2516 KB Output isn't correct
36 Correct 112 ms 3188 KB Output is correct
37 Correct 98 ms 3196 KB Output is correct
38 Incorrect 147 ms 3080 KB Output isn't correct
39 Correct 140 ms 4032 KB Output is correct
40 Correct 121 ms 3944 KB Output is correct
41 Incorrect 192 ms 3936 KB Output isn't correct
42 Correct 184 ms 4796 KB Output is correct
43 Correct 145 ms 4876 KB Output is correct
44 Incorrect 244 ms 4772 KB Output isn't correct
45 Correct 218 ms 5832 KB Output is correct
46 Correct 184 ms 5792 KB Output is correct
47 Incorrect 319 ms 5832 KB Output isn't correct
48 Correct 244 ms 6740 KB Output is correct
49 Correct 237 ms 6820 KB Output is correct
50 Incorrect 359 ms 6728 KB Output isn't correct
51 Correct 292 ms 8068 KB Output is correct
52 Correct 275 ms 7948 KB Output is correct
53 Incorrect 437 ms 7996 KB Output isn't correct
54 Correct 344 ms 9108 KB Output is correct
55 Correct 290 ms 9228 KB Output is correct
56 Incorrect 524 ms 9060 KB Output isn't correct
57 Correct 405 ms 10436 KB Output is correct
58 Correct 337 ms 10344 KB Output is correct
59 Incorrect 703 ms 10344 KB Output isn't correct
60 Correct 431 ms 11908 KB Output is correct
61 Correct 451 ms 11712 KB Output is correct
62 Incorrect 736 ms 11692 KB Output isn't correct
63 Correct 903 ms 11772 KB Output is correct
64 Execution timed out 1018 ms 11976 KB Time limit exceeded
65 Execution timed out 1036 ms 11816 KB Time limit exceeded
66 Correct 941 ms 11808 KB Output is correct
67 Incorrect 955 ms 11832 KB Output isn't correct
68 Correct 825 ms 11604 KB Output is correct
69 Incorrect 826 ms 11720 KB Output isn't correct
70 Incorrect 886 ms 11716 KB Output isn't correct
71 Incorrect 906 ms 11836 KB Output isn't correct
72 Incorrect 913 ms 11724 KB Output isn't correct
73 Incorrect 907 ms 11988 KB Output isn't correct
74 Correct 840 ms 11988 KB Output is correct
75 Execution timed out 1033 ms 11980 KB Time limit exceeded
76 Execution timed out 1043 ms 11976 KB Time limit exceeded
77 Correct 992 ms 11988 KB Output is correct
78 Incorrect 828 ms 11948 KB Output isn't correct
79 Correct 775 ms 11944 KB Output is correct
80 Correct 823 ms 12064 KB Output is correct
81 Correct 833 ms 11948 KB Output is correct
82 Correct 896 ms 11956 KB Output is correct
83 Correct 862 ms 11904 KB Output is correct
84 Correct 895 ms 11908 KB Output is correct
85 Execution timed out 1004 ms 11852 KB Time limit exceeded
86 Correct 908 ms 11980 KB Output is correct
87 Correct 810 ms 11904 KB Output is correct
88 Correct 836 ms 11844 KB Output is correct
89 Correct 853 ms 11960 KB Output is correct
90 Correct 939 ms 11956 KB Output is correct
91 Correct 795 ms 11852 KB Output is correct
92 Correct 828 ms 11980 KB Output is correct