oj.uz

Submission #753861

# Submission time Handle Problem Language Result Execution time Memory
753861 2023-06-06T08:38:02 Z jakobrs Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 16656 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <utility>

using i64 = int64_t;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    i64 n, m;
    std::cin >> n >> m;

    std::vector<i64> a(n);
    for (i64 i = 0; i < n; i++)
        std::cin >> a[i];

    std::vector<std::vector<i64>> adj(n);
    for (i64 i = 0; i < m; i++) {
        i64 u, v;
        std::cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::string result;
    result.reserve(n);

    std::vector<i64> visited(n);
    for (i64 i = 0; i < n; i++) {
        struct Node {
            i64 size;
            i64 idx;

            bool operator<(const Node &rhs) const {
                return std::tie(rhs.size, idx) < std::tie(size, rhs.idx);
            }
        };

        std::priority_queue<Node> q;
        std::fill(visited.begin(), visited.end(), false);
        visited[i] = true;

        i64 mass = a[i];
        q.push(Node { .size = 0, .idx = i });

        while (!q.empty()) {
            Node node = q.top();
            if (node.size > mass) break;
            mass += node.size;

            q.pop();
            for (i64 j : adj[node.idx]) {
                if (!visited[j]) {
                    visited[j] = true;
                    q.push(Node { .size = a[j], .idx = j });
                }
            }
        }

        result.push_back(q.empty() ? '1' : '0');
    }

    std::cout << result;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 157 ms 488 KB Output is correct
5 Correct 144 ms 496 KB Output is correct
6 Correct 216 ms 468 KB Output is correct
7 Correct 156 ms 488 KB Output is correct
8 Correct 103 ms 468 KB Output is correct
9 Correct 235 ms 520 KB Output is correct
10 Correct 65 ms 468 KB Output is correct
11 Correct 61 ms 468 KB Output is correct
12 Correct 61 ms 504 KB Output is correct
13 Correct 109 ms 580 KB Output is correct
14 Correct 95 ms 588 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1046 ms 16656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1058 ms 14572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1016 ms 16048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 157 ms 488 KB Output is correct
5 Correct 144 ms 496 KB Output is correct
6 Correct 216 ms 468 KB Output is correct
7 Correct 156 ms 488 KB Output is correct
8 Correct 103 ms 468 KB Output is correct
9 Correct 235 ms 520 KB Output is correct
10 Correct 65 ms 468 KB Output is correct
11 Correct 61 ms 468 KB Output is correct
12 Correct 61 ms 504 KB Output is correct
13 Correct 109 ms 580 KB Output is correct
14 Correct 95 ms 588 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 1046 ms 16656 KB Time limit exceeded
18 Halted 0 ms 0 KB -