Submission #1061458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061458		mc061	Keys (IOI21_keys)	C++17	37 / 100	1681 ms	16468 KiB

keys

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

const int N = 2e3+6;

vector<pair<int, int>> graph[N];

struct DSU {
    int p[N]={};
    int sz[N];
    DSU() {
        iota(p, p+N, 0);
        fill(sz, sz+N, 1);
    }
    int get(int a) {
        return p[a] = (a == p[a] ? a : get(p[a]));
    }
    void merge(int a, int b) {
        int x = get(a), y = get(b);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    const int n = r.size();
    const int m = u.size();
    for (int i = 0; i < m; ++i) {
        graph[v[i]].push_back({u[i], c[i]});
        graph[u[i]].push_back({v[i], c[i]});
    }

    vector<int> res(n);


    for (int s = 0; s < n; ++s) {
        DSU d;
        set<pair<int, int>> borders;
        queue<int> q;
        set<int> have;
        set<int> have_c;

        auto add = [&] (int v) {
            have.insert(v);
            if (!have_c.count(r[v])) {
                have_c.insert(r[v]);
                while (borders.size()) {
                    auto it = borders.lower_bound({r[v], -1});
                    if (it == borders.end()) break;
                    if (it->first == r[v]) {
                        d.merge(it->second, s);
                        if (!have.count(it->second)) {
                            have.insert(it->second);
                            q.push(it->second);
                        }
                        borders.erase(it);
                        continue;
                    }
                    break;
                }
            }
            for (auto [u, w] : graph[v]) {
                if (have.count(u)) continue;
                if (have_c.count(w)) {
                    q.push(u);
                    have.insert(u);
                    d.merge(s, u);
                    continue;
                }

                borders.insert({w, u});
            }
        };

        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            add(v);
        } 
        res[s] = d.sz[d.get(s)];
    }
    int mn = *min_element(res.begin(), res.end());
    vector<int> ret(n, 0);
    for (int i = 0; i < n; ++i) {
        if (res[i] == mn) ret[i] = 1;
    }
    return ret;
}

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