Submission #465992

#	Time	Username	Problem	Language	Result	Execution time	Memory
465992		alexxela12345	Keys (IOI21_keys)	C++17	100 / 100	1324 ms	81320 KiB

keys

//#pragma GCC optimize("Ofast,unroll-loops,fast-math,inline,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,avx,avx2,abm,mmx,popcnt")
#include <bits/stdc++.h>
using namespace std;

vector<int> pa;

void initDSU(int n) {
    pa.clear();
    pa.resize(n);
    iota(pa.begin(), pa.end(), 0);
}

int get(int v) {
    if (pa[v] == v)
        return v;
    return pa[v] = get(pa[v]);
}

void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b)
        return;
    pa[a] = pa[b];
}

int n;
vector<vector<pair<int, int>>> g;
vector<int> r;

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

    vector<int> used(n);
    vector<int> keys(n);
    vector<vector<int>> need(n);

    auto bfs = [&](int start) {
        vector<int> vs;
        deque<int> q;
        vector<int> needs;
        q.push_back(start);
        used[start] = 1;
        keys[r[start]] = 1;
        vs.push_back(start);
        while (!q.empty()) {
            int v = q.front();
            q.pop_front();
            for (auto [u, c] : g[v]) {
                if (!used[u]) {
                    if (keys[c]) {
                        used[u] = 1;
                        keys[r[u]] = 1;
                        q.push_back(u);
                        vs.push_back(u);
                        if (get(u) != get(start)) {
                            for (int v : vs) {
                                used[v] = 0;
                                keys[r[v]] = 0;
                                need[r[v]].clear();
                            }
                            for (int c : needs) {
                                need[c].clear();
                            }
                            return vs;
                        }
                        for (int z : need[r[u]]) {
                            if (!used[z]) {
                                used[z] = 1;
                                keys[r[z]] = 1;
                                q.push_back(z);
                                vs.push_back(z);
                                if (get(z) != get(start)) {
                                    for (int v : vs) {
                                        used[v] = 0;
                                        keys[r[v]] = 0;
                                        need[r[v]].clear();
                                    }
                                    for (int c : needs) {
                                        need[c].clear();
                                    }
                                    return vs;
                                }
                            }
                        }
                        need[r[u]].clear();
                    } else {
                        need[c].push_back(u);
                        needs.push_back(c);
                    }
                }
            }
        }
        for (int v : vs) {
            used[v] = 0;
            keys[r[v]] = 0;
            need[r[v]].clear();
        }
        for (int c : needs) {
            need[c].clear();
        }
        return vs;
    };
    initDSU(n);
    vector<vector<int>> ans;
    while (true) {
        vector<pair<int, int>> toMerge;
        for (int i = 0; i < n; i++) {
            if (get(i) != i)
                continue;
            vector<int> comp = bfs(i);
            if (get(comp.back()) != get(i)) {
                toMerge.push_back({i, comp.back()});
            } else {
                ans.push_back(comp);
            }
        }
        if (toMerge.empty())
            break;
        for (auto pp : toMerge) {
            merge(pp.first, pp.second);
        }
    }
    int minLen = n;
    for (auto &el : ans) {
        minLen = min(minLen, (int) el.size());
    }
    vector<int> ans2(n);
    for (auto &el : ans) {
        if ((int) el.size() == minLen) {
            for (int el2 : el) {
                ans2[el2] = 1;
            }
        }
    }
    return ans2;
}

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