Submission #597886

#	Time	Username	Problem	Language	Result	Execution time	Memory
597886		KoD	Keys (IOI21_keys)	C++17	100 / 100	1082 ms	150000 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> data;
    explicit UnionFind(const int n) : data(n, -1) {}
    int find(const int x) {
        return data[x] < 0 ? x : data[x] = find(data[x]);
    }
    int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (data[x] > data[y]) {
                swap(x, y);
            }
            data[x] += data[y];
            data[y] = x;
        }
        return x;
    }
};

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
    const int N = (int)size(R);
    const int M = (int)size(C);

    struct Data {
        vector<int> open;
        set<int> keys;
        map<int, vector<int>> locked;
        void add_edge(const int u, const int k) {
            if (keys.find(k) != end(keys)) {
                open.push_back(u);
            } else {
                locked[k].push_back(u);
            }
        }
        void add_key(const int x) {
            if (const auto itr = locked.find(x); itr != end(locked)) {
                for (const int u : itr->second) {
                    open.push_back(u);
                }
                locked.erase(itr);
            }
            keys.insert(x);
        }
    };

    UnionFind cycle(N);
    vector<Data> data(N);
    vector<int> status(N), toward(N), reach(N, N + 1);
    for (int i = 0; i < N; ++i) {
        data[i].keys.insert(R[i]);
    }
    for (int i = 0; i < M; ++i) {
        data[U[i]].add_edge(V[i], C[i]);
        data[V[i]].add_edge(U[i], C[i]);
    }

    for (int see = 0; see < N; ++see) {
        if (status[see] == 1) {
            continue;
        }
        vector<int> list;
        for (int u = see; status[u] != 1;) {
            if (status[u] == 0) {
                status[u] = -1;
                list.push_back(u);
            }
            if (data[u].open.empty()) {
                vector<int> same;
                for (const int x : list) {
                    if (cycle.find(x) == u) {
                        same.push_back(x);
                    }
                }
                const int n = (int)size(same);
                for (const int x : same) {
                    reach[x] = n;
                }
                break;
            }
            toward[u] = cycle.find(data[u].open.back());
            data[u].open.pop_back();
            if (status[toward[u]] == -1) {
                int v = u;
                while (true) {
                    v = cycle.find(toward[v]);
                    if (v == u) {
                        break;
                    }
                    const int r = cycle.merge(u, v);
                    const auto& move = data[r == u ? v : u];
                    u = r;
                    for (const int x : move.open) {
                        data[u].open.push_back(x);
                    }
                    for (const int x : move.keys) {
                        data[u].add_key(x);
                    }
                    for (const auto& [k, vec] : move.locked) {
                        for (const int x : vec) {
                            data[u].add_edge(x, k);
                        }
                    }
                }
            } else {
                u = toward[u];
            }
        }
        for (const int v : list) {
            // std::cerr << v << ' ';
            status[v] = 1;
        }
        // std::cerr << std::endl;
    }
    const int min = *min_element(begin(reach), end(reach));
    vector<int> ret(N);
    for (int i = 0; i < N; ++i) {
        ret[i] = min == reach[i];
    }
    return ret;
}

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