Submission #579158

#	Time	Username	Problem	Language	Result	Execution time	Memory
579158		KoD	열쇠 (IOI21_keys)	C++17	9 / 100	3079 ms	53312 KiB

keys

#include <vector>
#include <bits/stdc++.h>

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

using ll = long long;

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

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)...);
    }
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    const int N = (int)r.size();
    const int M = (int)u.size();
    const int K = std::max(*std::max_element(r.begin(), r.end()), *std::max_element(c.begin(), c.end())) + 1;
    vector<vector<pair<int, int>>> original_graph(N);
    vector<std::map<int, int>> graph(N);
    vector<std::set<int>> bad(N);
    for (int i = 0; i < M; ++i) {
        graph[u[i]].emplace(v[i], c[i]);
        graph[v[i]].emplace(u[i], c[i]);
        original_graph[u[i]].emplace_back(v[i], c[i]);
        original_graph[v[i]].emplace_back(u[i], c[i]);
    }
    vector<int> perm(N);
    std::iota(perm.begin(), perm.end(), 0);
    std::default_random_engine engine(904);
    std::shuffle(perm.begin(), perm.end(), engine);

    vector<char> found(K), prohibited(K);
    vector<vector<int>> waiting(K);
    vector<char> seen(N);
    vector<int> reach(N, N + 1);
    for (const int src : perm) {
        vector<int> visited, memo;
        std::queue<int> que;
        seen[src] = true;
        que.push(src);
        memo.push_back(src);
        if ([&]() -> bool {
            while (!que.empty()) {
                const int u = que.front();
                que.pop();
                visited.push_back(u);
                if (prohibited[r[u]]) {
                    return false;
                }
                found[r[u]] = true;
                for (const int v : waiting[r[u]]) {
                    que.push(v);
                }
                waiting[r[u]].clear();
                for (const auto& [v, c] : graph[u]) {
                    if (!seen[v]) {
                        seen[v] = true;
                        memo.push_back(v);
                        if (found[c]) {
                            que.push(v);
                        } else {
                            waiting[c].push_back(v);
                        }
                    }
                }
                for (const int c : bad[u]) {
                    if (found[c]) {
                        return false;
                    }
                    prohibited[c] = true;
                }
            }
            return true;
        }()) {
            const int n = (int)visited.size();
            for (const int u : visited) {
                reach[u] = std::min(reach[u], n);
            }
        } 
        for (const int u : memo) {
            seen[u] = false;
        }
        for (int i = 0; i < K; ++i) {
            found[i] = prohibited[i] = false;
            waiting[i].clear();
        }
        // for (const auto& [u, c] : original_graph[src]) {
        //     graph[u].erase(src);
        //     bad[u].insert(c);
        // }
    }
    const int min = *std::min_element(reach.begin(), reach.end());
    vector<int> ret(N);
    for (int i = 0; i < N; ++i) {
        ret[i] = reach[i] == min;
    }
    return ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33