oj.uz

Submission #581489

# Submission time Handle Problem Language Result Execution time Memory
581489 2022-06-22T17:03:53 Z Saeed_247 Mecho (IOI09_mecho) C++14
47 / 100
 233 ms 12368 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}};
const int N = 800;
bool visited[N][N];
long long n, s;
vector<vector<char>> arr;
vector<pair<long long, long long>> hives;
pair<long long, long long> m, d;
queue<pair<long long, long long>> q;

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

bool check(long long tim, vector<vector<long long>>& dist, vector<vector<long long>>& swarm) {
    memset(visited, false, sizeof visited);
    while (q.size()) q.pop();
    q.push(m);
    visited[m.first][m.second] = true;
    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') && !visited[x + xx][y + yy] && (dist[x + xx][y + yy] + tim < swarm[x + xx][y + yy] || 
                (dist[x + xx][y + yy] + tim == swarm[x + xx][y + yy] && dist[d.first][d.second] == dist[x + xx][y + yy]))) {
                q.push({x + xx, y + yy});
                visited[x + xx][y + yy] = true;
        }
    }
    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};
            }
        }
    }

    vector<vector<long long>> dist(n, vector<long long>(n, 1e18)), swarm(n, vector<long long>(n, 1e18));
    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);
        }
    }
    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});
        }
    }

    long long l = 0, h = 640000;
    while (h - l > 1) {
        int mid = (h + l) / 2;
        if (check(mid, dist, swarm)) l = mid;
        else h = mid;
    }
    cout << l << '\n';
    return 0;
}

Compilation message

mecho.cpp: In function 'bool check(long long int, std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&)':
mecho.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         auto [x, y] = q.front();
      |              ^
mecho.cpp:34:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for (auto [xx, yy] : dir) if (move(x + xx, y + yy) && (arr[x + xx][y + yy] == 'G' ||
      |                   ^
mecho.cpp: In function 'int main()':
mecho.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         auto [x, y] = q.front();
      |              ^
mecho.cpp:69:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for (auto [xx, yy] : dir) if (move(x + xx, y + yy) && (arr[x + xx][y + yy] == 'G' ||
      |                   ^
mecho.cpp:80:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for (auto [x, y] : hives) {
      |               ^
mecho.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto [x, y] = q.front();
      |              ^
mecho.cpp:87:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         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) {
      |                   ^

Subtask #1
47.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 126 ms 11904 KB Output is correct
8 Incorrect 1 ms 852 KB Output isn't correct
9 Incorrect 1 ms 852 KB Output isn't correct
10 Incorrect 1 ms 852 KB Output isn't correct
11 Incorrect 1 ms 852 KB Output isn't correct
12 Incorrect 1 ms 980 KB Output isn't correct
13 Correct 1 ms 904 KB Output is correct
14 Incorrect 1 ms 980 KB Output isn't correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 1 ms 980 KB Output is correct
24 Correct 1 ms 980 KB Output is correct
25 Correct 1 ms 980 KB Output is correct
26 Correct 1 ms 980 KB Output is correct
27 Correct 1 ms 980 KB Output is correct
28 Correct 1 ms 980 KB Output is correct
29 Correct 1 ms 980 KB Output is correct
30 Correct 1 ms 980 KB Output is correct
31 Correct 1 ms 980 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 7 ms 3028 KB Output is correct
34 Correct 6 ms 2900 KB Output is correct
35 Incorrect 21 ms 3040 KB Output isn't correct
36 Correct 10 ms 3648 KB Output is correct
37 Correct 9 ms 3540 KB Output is correct
38 Incorrect 28 ms 3668 KB Output isn't correct
39 Correct 12 ms 4308 KB Output is correct
40 Correct 11 ms 4308 KB Output is correct
41 Incorrect 51 ms 4268 KB Output isn't correct
42 Correct 13 ms 5076 KB Output is correct
43 Correct 13 ms 5128 KB Output is correct
44 Incorrect 45 ms 5076 KB Output isn't correct
45 Correct 15 ms 5972 KB Output is correct
46 Correct 16 ms 5940 KB Output is correct
47 Incorrect 54 ms 5972 KB Output isn't correct
48 Correct 19 ms 6896 KB Output is correct
49 Correct 18 ms 6996 KB Output is correct
50 Incorrect 100 ms 6992 KB Output isn't correct
51 Correct 23 ms 7944 KB Output is correct
52 Correct 23 ms 7948 KB Output is correct
53 Incorrect 90 ms 7948 KB Output isn't correct
54 Correct 26 ms 9076 KB Output is correct
55 Correct 26 ms 9172 KB Output is correct
56 Incorrect 114 ms 9180 KB Output isn't correct
57 Correct 33 ms 10316 KB Output is correct
58 Correct 30 ms 10272 KB Output is correct
59 Incorrect 131 ms 10288 KB Output isn't correct
60 Correct 33 ms 11596 KB Output is correct
61 Correct 31 ms 11568 KB Output is correct
62 Incorrect 146 ms 11684 KB Output isn't correct
63 Correct 158 ms 11692 KB Output is correct
64 Incorrect 233 ms 11712 KB Output isn't correct
65 Incorrect 227 ms 11696 KB Output isn't correct
66 Correct 173 ms 11592 KB Output is correct
67 Incorrect 159 ms 11688 KB Output isn't correct
68 Correct 78 ms 11636 KB Output is correct
69 Incorrect 71 ms 11716 KB Output isn't correct
70 Incorrect 66 ms 11612 KB Output isn't correct
71 Incorrect 71 ms 11728 KB Output isn't correct
72 Incorrect 63 ms 11724 KB Output isn't correct
73 Incorrect 99 ms 12272 KB Output isn't correct
74 Correct 81 ms 12112 KB Output is correct
75 Correct 96 ms 12224 KB Output is correct
76 Correct 97 ms 12168 KB Output is correct
77 Correct 102 ms 12156 KB Output is correct
78 Incorrect 100 ms 12368 KB Output isn't correct
79 Correct 78 ms 12140 KB Output is correct
80 Correct 102 ms 12176 KB Output is correct
81 Correct 96 ms 12184 KB Output is correct
82 Correct 84 ms 12124 KB Output is correct
83 Correct 114 ms 12144 KB Output is correct
84 Correct 98 ms 12124 KB Output is correct
85 Correct 119 ms 12248 KB Output is correct
86 Correct 113 ms 12152 KB Output is correct
87 Correct 106 ms 12120 KB Output is correct
88 Correct 114 ms 12012 KB Output is correct
89 Correct 155 ms 11984 KB Output is correct
90 Correct 115 ms 11976 KB Output is correct
91 Correct 114 ms 12016 KB Output is correct
92 Correct 112 ms 11976 KB Output is correct