Submission #780509

#	Time	Username	Problem	Language	Result	Execution time	Memory
780509		jakobrs	Stranded Far From Home (BOI22_island)	C++17	20 / 100	197 ms	38480 KiB

island

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
#include <numeric>

using i64 = int64_t;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    i64 n, m;
    std::cin >> n >> m;

    std::vector<i64> a(n);
    for (i64 i = 0; i < n; i++) std::cin >> a[i];

    std::vector<std::vector<i64>> adj(n);
    std::vector<std::vector<i64>> children(n);
    for (i64 i = 0; i < m; i++) {
        i64 u, v;
        std::cin >> u >> v;
        u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);

        children[std::min(u, v)].push_back(std::max(u, v));
    }

    bool s = true;
    for (i64 i = 0; i < n; i++) {
        for (i64 j : children[i]) {
            if (a[j] > a[i]) {
                s = false;
                goto bad;
            }
        }
    }
bad:;

    if (n <= 2000 && m <= 2000) {
        std::string result;
        result.reserve(n);

        std::vector<i64> visited(n);
        for (i64 i = 0; i < n; i++) {
            struct Node {
                i64 size;
                i64 idx;

                bool operator<(const Node &rhs) const {
                    return std::tie(rhs.size, idx) < std::tie(size, rhs.idx);
                }
            };

            std::priority_queue<Node> q;
            std::fill(visited.begin(), visited.end(), false);
            visited[i] = true;

            i64 mass = a[i];
            q.push(Node{.size = 0, .idx = i});

            while (!q.empty()) {
                Node node = q.top();
                if (node.size > mass) break;
                mass += node.size;

                q.pop();
                for (i64 j : adj[node.idx]) {
                    if (!visited[j]) {
                        visited[j] = true;
                        q.push(Node{.size = a[j], .idx = j});
                    }
                }
            }

            result.push_back(q.empty() ? '1' : '0');
        }

        std::cout << result;
    } else if (s) {
        std::string result(n, '0');

        std::vector<i64> sizes(n);
        for (i64 i = n - 1; i >= 0; i--) {
            sizes[i] = a[i];

            for (i64 j : children[i]) {
                sizes[i] += sizes[j];
            }
        }

        result[0] = '1';

        for (i64 i = 0; i < n; i++) {
            if (result[i] == '1') {
                for (i64 j : children[i]) {
                    if (sizes[j] >= a[i]) {
                        result[j] = '1';
                    }
                }
            }
        }

        std::cout << result;
    } else {
        struct Node {
            i64 max;
            i64 acc;
            std::vector<Node> replaces;

            Node(i64 max, i64 acc, std::vector<Node> &&replaces) : max(max), acc(acc), replaces(std::move(replaces)) {}

            // void visualise(std::string prefix) const {
            //     std::cout << prefix << "max: " << max << '\n';
            //     std::cout << prefix << "acc: " << acc << "\n";
            //     std::cout << prefix << "replaces:\n";
            //     for (const Node &node : replaces) {
            //         node.visualise(prefix + "  ");
            //     }
            // }
        };

        std::vector<Node> ltr;
        ltr.push_back({(i64)200'000 * (i64)1'000'000 + (i64)100, 0, {}});
        for (i64 x : a) {
            std::vector<Node> replaces;
            i64 acc = ltr.back().acc;
            while (x >= ltr.back().max) {
                replaces.push_back(std::move(ltr.back()));
                ltr.pop_back();
            }
            ltr.emplace_back(
                /* max */ x,
                /* acc */ acc - x,
                /* replaces */ std::move(replaces));
        }

        i64 total = std::accumulate(a.begin(), a.end(), 0);

        std::string result(n, '0');

        std::vector<std::pair<i64, i64>> rtl;
        rtl.push_back({(i64)200'000 * (i64)1'000'000 + (i64)100, 0});
        for (i64 i = 0; i < n; i++) {
            i64 x = a[n - i - 1];

            // std::cout << n - i - 1 << '\n';
            // for (auto [x, y] : rtl) {
            //     std::cout << x << ' ' << y << '\n';
            // }

            std::vector<Node> replaced = std::move(ltr.back().replaces);
            ltr.pop_back();
            for (i64 i = 0; i < replaced.size(); i++) {
                ltr.push_back(std::move(replaced[replaced.size() - i - 1]));
            }

            // for (const Node &node : ltr) {
            //     node.visualise("");
            // }

            i64 mass = x;
            auto rightwards = rtl.rbegin();
            auto leftwards = ltr.rbegin();
            while (true) {
                bool either = false;
                // try going right
                auto it =
                    std::upper_bound(rtl.rbegin(), rtl.rend(), mass,
                                     [](i64 mass, std::pair<i64, i64> pair) {
                                         return mass < pair.first;
                                     });

                if (std::distance(rightwards, it) > 0) {
                    either = true;
                    mass += it->second - rightwards->second;
                    rightwards = it;
                }

                auto rit = std::upper_bound(
                    ltr.rbegin(), ltr.rend(), mass,
                    [](i64 mass, const Node &node) { return mass < node.max; });

                if (std::distance(leftwards, rit) > 0) {
                    either = true;
                    mass += rit->acc - leftwards->acc;
                    leftwards = rit;
                }

                if (!either) break;
            }

            if (mass == total) {
                result[n - i - 1] = '1';
            }

            // std::cout << "converted " << mass << " people\n";

            i64 acc = rtl.back().second;
            while (x >= rtl.back().first) {
                rtl.pop_back();
            }
            rtl.push_back({x, acc - x});
        }

        std::cout << result;
    }
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:158:31: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<main()::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |             for (i64 i = 0; i < replaced.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~

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