Submission #759310

#	Time	Username	Problem	Language	Result	Execution time	Memory
759310		drdilyor	Keys (IOI21_keys)	C++17	37 / 100	3031 ms	24052 KiB

keys

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

struct DSU {
    int n;
    vector<int> parent;
    vector<int> size;
    vector<vector<int>> set;

    DSU(int n) : n(n), parent(n), size(n, 1),set(n) {
        for (int i = 0; i < n ;i++)
            parent[i] = i, set[i] = {i};
    }

    int get(int i) {
        return parent[i] == i ? i : parent[i] = get(parent[i]);
    }

    void merge(int v, int u) {
        v = get(v);
        u = get(u);
        if (u == v) return;
        if (size[v] < size[u]) swap(v, u);
        parent[u] = v;
        size[v] += size[u];
        for (int i : set[u])set[v].push_back(i);
    }
};


vi find_reachable(vi r, vi u, vi v, vi c) {
    int n = r.size();
    int m = u.size();
    vector<vi> byc(n);
    for (int i = 0; i < m; i++)
        byc[c[i]].push_back(i);
    vi count(n);
    for (int root = 0; root < n; root++) {
        DSU cc(n);
        vi obtained(n);
        vi new_keys;
        obtained[r[root]] = 1;
        new_keys.push_back(r[root]);
        while (new_keys.size()) {
            vi keys = std::move(new_keys);
            for (int i : keys) {
                for (int j : byc[i]) {
                    if (cc.get(v[j]) == cc.get(u[j])) continue;
                    if (cc.get(u[j]) == cc.get(root))
                        swap(v[j], u[j]);
                    if (cc.get(v[j]) == cc.get(root)) {
                        for (int k : cc.set[cc.get(u[j])])
                            if (!obtained[r[k]]) {
                                obtained[r[k]] = 1;
                                new_keys.push_back(r[k]);
                            }
                    }
                    cc.merge(v[j], u[j]);
                }
            }
        }
        count[root] = cc.size[cc.get(root)];
    }
    vi ans(n);
    int mn = *min_element(count.begin(), count.end());
    for (int i = 0;i < n;i++)
        ans[i] = count[i] == mn;
    return ans;
}

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