Submission #793568

#	Time	Username	Problem	Language	Result	Execution time	Memory
793568		skittles1412	장난감 기차 (IOI17_train)	C++17	100 / 100	715 ms	1556 KiB

train

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << " ";
        }
        out << arr[i];
    }
    return out << "]";
}

vector<int> solve_must_vis(const vector<pair<int, int>>& edges,
                           const vector<vector<int>>& igraph,
                           const vector<int>& arr,
                           int team,
                           const vector<int>& nodes) {
    int n = sz(arr);

    int o_deg[n] {};
    for (auto& [u, v] : edges) {
        o_deg[u]++;
    }

    int co_deg[n] {};
    bool queued[n] {};
    vector<int> q;

    auto push = [&](int u) -> void {
        if (queued[u]) {
            return;
        }
        queued[u] = true;
        q.push_back(u);
    };
    for (auto& a : nodes) {
        push(a);
    }

    while (sz(q)) {
        int u = q.back();
        q.pop_back();

        for (auto& v : igraph[u]) {
            co_deg[v]++;
            if (arr[v] == team) {
                push(v);
            } else {
                if (co_deg[v] == o_deg[v]) {
                    push(v);
                }
            }
        }
    }

    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (queued[i]) {
            ans.push_back(i);
        }
    }
    return ans;
}

vector<int> who_wins(vector<int> arr,
                     vector<int> is_charging,
                     vector<int> edges_u,
                     vector<int> edges_v) {
    int n = sz(arr), m = sz(edges_u);

    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++) {
        edges.emplace_back(edges_u[i], edges_v[i]);
    }

    vector<vector<int>> igraph(n);
    for (auto& [u, v] : edges) {
        igraph[v].push_back(u);
    }

    for (int iter = 0; iter <= n; iter++) {
        vector<int> charging;
        for (int i = 0; i < n; i++) {
            if (is_charging[i]) {
                charging.push_back(i);
            }
        }
        auto must_charge = solve_must_vis(edges, igraph, arr, 1, charging);
        dbg(must_charge);

        bool is_must_charge[n] {};
        for (auto& a : must_charge) {
            is_must_charge[a] = true;
        }
        vector<int> wont_charge;
        for (int i = 0; i < n; i++) {
            if (!is_must_charge[i]) {
                wont_charge.push_back(i);
            }
        }

        auto all_wont_charge =
            solve_must_vis(edges, igraph, arr, 0, wont_charge);
        bool c_wont_charge[n] {};
        for (auto& a : all_wont_charge) {
            c_wont_charge[a] = true;
        }
        bool changed = false;
        for (auto& a : charging) {
            if (c_wont_charge[a]) {
                is_charging[a] = false;
                changed = true;
            }
        }

        if (changed) {
            continue;
        }
        vector<int> ans(n, 1);
        for (auto& a : all_wont_charge) {
            ans[a] = 0;
        }
        return ans;
    }

    assert(false);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51