Submission #588765

#	Time	Username	Problem	Language	Result	Execution time	Memory
588765		PurpleCrayon	Keys (IOI21_keys)	C++17	0 / 100	11 ms	21460 KiB

keys

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;

int n, m;
vector<ar<int, 2>> adj[N];

int par[N], sz[N];
set<int> cols[N]; // the colors that the current node contains

int f[N]; // parent of tree
int up[N]; // root of tree
int vis[N];
set<int> roots; // set of all roots

int find_set(int v) {
    return par[v] == v ? v : par[v] = find_set(par[v]);
}
// stuff to update:
//      - cols
//      - roots
//          - if stuff is unioned, it can't be dead
//      - adj

int union_sets(int a, int b) {
    a = find_set(a), b = find_set(b);
    if (a == b) return -1;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b], sz[b] = 0;

    roots.erase(b), roots.insert(a);
    for (int x : cols[b]) cols[a].insert(x);
    for (auto nxt : adj[b]) adj[a].push_back(nxt);
    adj[b].clear(), cols[b].clear();

    return a;
}
int recalc_up(int c) {
    if (up[c] != -1) return up[c];
    return up[c] = recalc_up(f[c]);
}
vector<int> find_reachable(vector<int> r, vector<int> _u, vector<int> _v, vector<int> _c) {
    n = sz(r), m = sz(_c);
    for (int i = 0; i < m; i++) {
        int a = _u[i], b = _v[i], x = _c[i];
        adj[a].push_back({b, x});
        adj[b].push_back({a, x});
    }
    std::iota(par, par + n, 0);
    std::fill(sz, sz + n, 1);
    for (int i = 0; i < n; i++) {
        cols[i].insert(r[i]);
        roots.insert(i);
    }


    set<int> done;
    while (sz(roots)) {
        for (int c : roots) {
            assert(c == find_set(c));
            f[c] = -1;
            for (auto [nxt, x] : adj[c]) if (find_set(nxt) != find_set(c) && cols[c].count(x)) {
                f[c] = find_set(nxt);
                break;
            }
            if (f[c] == -1) done.insert(c);
            else if (done.count(find_set(f[c]))) {
                f[c] = -1;
            }

            vis[c] = -1;
            up[c] = c;
        }

        set<int> cyc_root;
        for (int c : roots) if (!done.count(c) && vis[c] == -1) {
            bool mark = 0;
            int cur = c;
            while (vis[cur] == -1) {
                vis[cur] = c;
                if (f[cur] == -1) {
                    mark = 1;
                    break;
                }
                cur = find_set(up[f[cur]]);
            }
            if (mark) { // can reach a dead thing, so must be killed
                int start = c;
                while (start != cur) {
                    int nxt = f[start];
                    f[start] = -1;
                    start = find_set(nxt);
                }
                continue;
            }
            if (vis[cur] == c) {
                cyc_root.insert(cur);
            }
        }
        map<int, int> cyc; // node, cyc root
        for (int c : cyc_root) {
            cyc[c] = c;
            int cur = find_set(f[c]);
            while (cur != c) {
                cyc[cur] = c;
                cur = find_set(f[cur]);
            }
        }

        // recalculate up
        vector<int> dead_roots;
        for (int c : roots) if (!cyc.count(c)) {
            dead_roots.push_back(c);
            up[c] = -1;
        }
        for (int c : dead_roots) {
            if (f[c] != -1) {
                recalc_up(c);
            }
            roots.erase(c);
        }

        // merge the new roots
        for (auto [a, b] : cyc) {
            union_sets(a, b);
        }
    }
    int ret = n + 1;
    for (int c : done) {
        assert(c == find_set(c));
        ret = min(ret, sz[c]);
    }

    vector<int> ans(n);
    for (int i = 0; i < n; i++) if (done.count(find_set(i)) && sz[find_set(i)] == ret) ans[i] = 1;
    return ans;
}

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