제출 #582012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582012		KoD	Stranded Far From Home (BOI22_island)	C++17	100 / 100	252 ms	31276 KiB

island

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

struct UnionFind {
    vector<int> par;
    explicit UnionFind(const int n) : par(n, -1) {}
    int find(int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    pair<int, bool> merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return {u, false};
        }
        if (par[u] > par[v]) {
            std::swap(u, v);
        }
        par[u] += par[v];
        par[v] = u;
        return {u, true};
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<int> P(N);
    for (auto& x : P) {
        std::cin >> x;
    }
    vector<vector<int>> graph(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        std::cin >> u >> v;
        u -= 1, v -= 1;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
        return P[i] < P[j];
    });
    vector<char> seen(N);
    vector<int> ans(N, 1);
    UnionFind dsu(N);
    vector<vector<int>> list(N);
    vector<ll> sum(N);
    for (const int u : ord) {
        vector<int> new_list = {u};
        ll new_sum = P[u];
        int root = u;
        for (const int v : graph[u]) {
            if (seen[v]) {
                const int vr = dsu.find(v);
                const auto [w, f] = dsu.merge(u, vr);
                if (f) {
                    if (sum[vr] >= P[u]) {
                        auto& add = list[vr];
                        if (add.size() > new_list.size()) {
                            std::swap(add, new_list);
                        }
                        for (const int x : add) {
                            new_list.push_back(x);
                        }
                    } else {
                        for (const int x : list[vr]) {
                            ans[x] = false;
                        }
                    }
                    new_sum += sum[vr];
                    root = w;
                }
            }
        }
        list[root] = std::move(new_list);
        sum[root] = new_sum;
        seen[u] = true;
    }
    for (const int x : ans) {
        std::cout << x;
    }
    std::cout << '\n';
    return 0;
}

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