oj.uz

Submission #769414

# Submission time Handle Problem Language Result Execution time Memory
769414 2023-06-29T14:20:06 Z borisAngelov Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 18336 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int maxn = 200005;

int n, m;

long long people[maxn];

vector<int> g[maxn];

bool answer[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> people[i];
    }

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i)
    {
        long long sum = people[i];

        vector<bool> visited(n + 5, false);
        visited[i] = true;

        priority_queue<pair<long long, int>> pq;
        pq.push(make_pair(0, i));

        bool flag = true;

        while (!pq.empty())
        {
            pair<long long, int> p = pq.top();
            pq.pop();

            long long curr = -p.first;
            int node = p.second;

            visited[node] = true;

            if (sum < curr)
            {
                flag = false;
                break;
            }

            sum += curr;

            for (auto next_node : g[node])
            {
                if (visited[next_node] == false)
                {
                    pq.push(make_pair(-people[next_node], next_node));
                }
            }
        }

        for (int j = 1; j <= n; ++j)
        {
            if (visited[i] == false)
            {
                flag = false;
                break;
            }
        }

        answer[i] = flag;
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << answer[i];
    }

    cout << endl;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 193 ms 5132 KB Output is correct
5 Correct 134 ms 5076 KB Output is correct
6 Correct 325 ms 5136 KB Output is correct
7 Correct 216 ms 5076 KB Output is correct
8 Correct 162 ms 5076 KB Output is correct
9 Correct 206 ms 5156 KB Output is correct
10 Correct 52 ms 5136 KB Output is correct
11 Correct 50 ms 5076 KB Output is correct
12 Correct 48 ms 5136 KB Output is correct
13 Correct 91 ms 5176 KB Output is correct
14 Correct 93 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 1077 ms 18336 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 193 ms 5132 KB Output is correct
5 Correct 134 ms 5076 KB Output is correct
6 Correct 325 ms 5136 KB Output is correct
7 Correct 216 ms 5076 KB Output is correct
8 Correct 162 ms 5076 KB Output is correct
9 Correct 206 ms 5156 KB Output is correct
10 Correct 52 ms 5136 KB Output is correct
11 Correct 50 ms 5076 KB Output is correct
12 Correct 48 ms 5136 KB Output is correct
13 Correct 91 ms 5176 KB Output is correct
14 Correct 93 ms 5076 KB Output is correct
15 Correct 2 ms 5032 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1077 ms 18336 KB Time limit exceeded
18 Halted 0 ms 0 KB -