oj.uz

Submission #780509

# Submission time Handle Problem Language Result Execution time Memory
780509 2023-07-12T09:41:31 Z jakobrs Stranded Far From Home (BOI22_island) C++17
20 / 100
 197 ms 38480 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 153 ms 572 KB Output is correct
5 Correct 151 ms 596 KB Output is correct
6 Correct 197 ms 544 KB Output is correct
7 Correct 161 ms 576 KB Output is correct
8 Correct 108 ms 468 KB Output is correct
9 Correct 162 ms 600 KB Output is correct
10 Correct 51 ms 596 KB Output is correct
11 Correct 48 ms 596 KB Output is correct
12 Correct 49 ms 584 KB Output is correct
13 Correct 95 ms 580 KB Output is correct
14 Correct 85 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 143 ms 29124 KB Output is correct
4 Correct 118 ms 27800 KB Output is correct
5 Correct 136 ms 28080 KB Output is correct
6 Correct 129 ms 28936 KB Output is correct
7 Correct 185 ms 28976 KB Output is correct
8 Correct 154 ms 29020 KB Output is correct
9 Correct 164 ms 29164 KB Output is correct
10 Correct 66 ms 26156 KB Output is correct
11 Correct 65 ms 25968 KB Output is correct
12 Correct 131 ms 27596 KB Output is correct
13 Correct 103 ms 28548 KB Output is correct
14 Correct 119 ms 28800 KB Output is correct
15 Correct 116 ms 30168 KB Output is correct
16 Correct 65 ms 29140 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 134 ms 38480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 137 ms 37268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 153 ms 572 KB Output is correct
5 Correct 151 ms 596 KB Output is correct
6 Correct 197 ms 544 KB Output is correct
7 Correct 161 ms 576 KB Output is correct
8 Correct 108 ms 468 KB Output is correct
9 Correct 162 ms 600 KB Output is correct
10 Correct 51 ms 596 KB Output is correct
11 Correct 48 ms 596 KB Output is correct
12 Correct 49 ms 584 KB Output is correct
13 Correct 95 ms 580 KB Output is correct
14 Correct 85 ms 468 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 143 ms 29124 KB Output is correct
18 Correct 118 ms 27800 KB Output is correct
19 Correct 136 ms 28080 KB Output is correct
20 Correct 129 ms 28936 KB Output is correct
21 Correct 185 ms 28976 KB Output is correct
22 Correct 154 ms 29020 KB Output is correct
23 Correct 164 ms 29164 KB Output is correct
24 Correct 66 ms 26156 KB Output is correct
25 Correct 65 ms 25968 KB Output is correct
26 Correct 131 ms 27596 KB Output is correct
27 Correct 103 ms 28548 KB Output is correct
28 Correct 119 ms 28800 KB Output is correct
29 Correct 116 ms 30168 KB Output is correct
30 Correct 65 ms 29140 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Incorrect 134 ms 38480 KB Output isn't correct
33 Halted 0 ms 0 KB -