제출 #769414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769414		borisAngelov	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1078 ms	18336 KiB

island

#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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35