Submission #694979

#	Time	Username	Problem	Language	Result	Execution time	Memory
694979		finn__	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1085 ms	18948 KiB

island

#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<pair<unsigned, unsigned>> p(n);
    for (size_t i = 0; i < n; i++)
        p[i] = {s[i], i};
    sort(p.begin(), p.end());

    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 (auto const &[___, i] : p)
    {
        if (z[i])
            continue;

        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;

        if (z[i])
        {
            queue<unsigned> q;
            for (unsigned const &v : g[i])
                if (s[v] >= s[i] && !z[v])
                    q.push(v);
            while (!q.empty())
            {
                z[q.front()] = 1;
                for (unsigned const &v : g[q.front()])
                    if (s[v] >= s[q.front()] && !z[v])
                        q.push(v);
                q.pop();
            }
        }
    }

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35