Submission #694977

#	Time	Username	Problem	Language	Result	Execution time	Memory
694977		finn__	Stranded Far From Home (BOI22_island)	C++17	10 / 100	246 ms	13404 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<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);
    }

    if (n > 2000)
    {
        unsigned presum = s[n - 1];
        string y;
        y.resize(n);
        for (size_t i = n - 1; i < n; i--)
        {
            if (!i || presum >= s[i - 1])
                y[i] = '1';
            else
                y[i] = '0';
            presum += i ? s[i - 1] : 0;
        }
        cout << y << '\n';
        return 0;
    }

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