Submission #768907

#	Time	Username	Problem	Language	Result	Execution time	Memory
768907		PurpleCrayon	Keys (IOI21_keys)	C++17	100 / 100	1348 ms	194780 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;

struct DSU {
    vector<int> par, sz;
    DSU(int n): par(n) {
        iota(par.begin(), par.end(), 0);
        sz.assign(n, 1);
    }

    int find_set(int v) {
        return v == par[v] ? v : par[v] = find_set(par[v]);
    }

    bool union_sets(int a, int b) {
        if ((a = find_set(a)) == (b = find_set(b))) return false;
        if (sz[a] < sz[b]) swap(a, b);
        par[b] = a, sz[a] += sz[b], sz[b] = 0;
        return true;
    }
};

int n, m, my_out[N];
int par[N];
vector<int> st[N];
set<int> has[N];
map<int, vector<int>> by_col[N];
set<int> both[N];
vector<ar<int, 2>> adj[N];

void merge(int a, int b) {
    a = par[a], b = par[b];
    if (a == b) return;
    if (sz(st[a]) < sz(st[b])) swap(a, b);

    for (int x : st[b]) {
        st[a].push_back(x);
        par[x] = a;
    }
    st[b].clear();

    for (int x : has[b]) {
        has[a].insert(x);

        if (sz(by_col[a][x])) {
            both[a].insert(x);
        }
    }
    has[b].clear();

    for (auto [x, v] : by_col[b]) {
        if (!sz(v)) continue;

        vector<int>& base = by_col[a][x];
        for (int y : v) {
            base.push_back(y);
        }

        if (has[a].count(x)) {
            both[a].insert(x);
        }
    }
    by_col[b].clear();
    both[b].clear();
}

int get_out(int c) {
    c = par[c];

    int ans = -1;
    vector<int> done;
    for (int x : both[c]) {
        vector<int>& v = by_col[c][x];
        while (sz(v)) {
            if (par[v.back()] == c) {
                v.pop_back();
            } else {
                ans = par[v.back()];
                goto found;
            }
        }

        done.push_back(x);
    }
found:
    for (int x : done) both[c].erase(x);
    return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = sz(r), m = sz(u);
    memset(my_out, -1, sizeof(my_out));
    for (int i = 0; i < n; i++) {
        par[i] = i;
        st[i].push_back(i);
        has[i].insert(r[i]);
    }

    for (int i = 0; i < m; i++) {
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }

    for (int i = 0; i < n; i++) {
        for (auto [nxt, w] : adj[i]) {
            by_col[i][w].push_back(nxt);
        }

        for (int x : has[i]) if (sz(by_col[i][x])) {
            both[i].insert(x);
        }
    }

    DSU d(n);
    for (int root = 0; root < n; root++) {
        my_out[par[root]] = get_out(root);
        while (my_out[par[root]] != -1) {
            if (d.union_sets(root, my_out[par[root]])) {
                break;
            } else {
                vector<int> use{par[my_out[par[root]]]};
                while (use.back() != par[root]) {
                    use.push_back(par[my_out[use.back()]]);
                }

                use.pop_back();
                for (int x : use) {
                    merge(x, root);
                }
                my_out[par[root]] = get_out(root);
            }
        }
    }

    int best = MOD;
    for (int i = 0; i < n; i++) {
        int c = par[i];
        if (my_out[c] == -1) {
            best = min(best, sz(st[c]));
        }
    }

    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        int c = par[i];
        if (my_out[c] == -1 && sz(st[c]) == best) {
            ans[i] = 1;
        }
    }
	return ans;
}

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