oj.uz

Submission #694971

# Submission time Handle Problem Language Result Execution time Memory
694971 2023-02-04T16:04:25 Z finn__ Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 17952 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    size_t n, m;
    cin >> n >> m;

    vector<uint64_t> s(n);
    uint64_t total_size = 0;
    for (uint64_t &x : s)
        cin >> x, total_size += x;

    vector<vector<unsigned>> g(n);
    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    vector<bool> z(n, 0);

    for (unsigned i = 0; i < n; i++)
    {
        priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>, greater<pair<unsigned, unsigned>>> q;
        vector<bool> visited(n, 0);
        visited[i] = 1;
        uint64_t curr_size = s[i];
        for (unsigned const &v : g[i])
            q.emplace(s[v], v), visited[v] = 1;

        while (!q.empty())
        {
            auto const [x, u] = q.top();
            q.pop();
            if (x > curr_size)
                break;
            curr_size += x;
            for (unsigned const &v : g[u])
                if (!visited[v])
                {
                    q.emplace(s[v], v);
                    visited[v] = 1;
                }
        }

        z[i] = curr_size == total_size;
    }

    for (size_t i = 0; i < n; i++)
        cout << (unsigned)z[i];
    cout << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 142 ms 432 KB Output is correct
5 Correct 133 ms 444 KB Output is correct
6 Correct 185 ms 416 KB Output is correct
7 Correct 141 ms 420 KB Output is correct
8 Correct 96 ms 460 KB Output is correct
9 Correct 188 ms 444 KB Output is correct
10 Correct 58 ms 436 KB Output is correct
11 Correct 53 ms 440 KB Output is correct
12 Correct 58 ms 448 KB Output is correct
13 Correct 100 ms 436 KB Output is correct
14 Correct 82 ms 428 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 300 KB Output is correct
3 Execution timed out 1083 ms 17952 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Execution timed out 1076 ms 17128 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 296 KB Output is correct
2 Execution timed out 1071 ms 17388 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 0 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 142 ms 432 KB Output is correct
5 Correct 133 ms 444 KB Output is correct
6 Correct 185 ms 416 KB Output is correct
7 Correct 141 ms 420 KB Output is correct
8 Correct 96 ms 460 KB Output is correct
9 Correct 188 ms 444 KB Output is correct
10 Correct 58 ms 436 KB Output is correct
11 Correct 53 ms 440 KB Output is correct
12 Correct 58 ms 448 KB Output is correct
13 Correct 100 ms 436 KB Output is correct
14 Correct 82 ms 428 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Execution timed out 1083 ms 17952 KB Time limit exceeded
18 Halted 0 ms 0 KB -