Submission #1063078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063078		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	3040 ms	139628 KiB

keys

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct nod {
    set<int> Noduri;
    set<int> Cul;

    set<ii> MuchiiActive;
    set<ii> MuchiiFol;
    set<ii> MuchiiInactive; // (cul, to)
    ///multiset<int> Wishlist; < pt optimizare
    
    bool empty() { return MuchiiActive.empty(); }

    ii get_muchie() {
        auto it = *MuchiiActive.begin();
        MuchiiActive.erase(it);
        MuchiiFol.insert(it);
        return it;
    }

    int size() { return int(Noduri.size()); }

    void add_edge(int to, int c) {
        if(Cul.count(c)) {
            MuchiiActive.insert({c, to});
        } else {
            MuchiiInactive.insert({c, to});
        }
    }
};

void join_nod(nod &a, nod &b) {
    ///va pune info din b in a
    for(auto it : b.Noduri)
        a.Noduri.insert(it);
    for(auto it : b.Cul)
        a.Cul.insert(it);
    for(auto it : b.MuchiiFol)
        a.MuchiiFol.insert(it);
    for(auto it : b.MuchiiActive)
        a.MuchiiActive.insert(it);
    for(auto it : b.MuchiiInactive)
        a.MuchiiInactive.insert(it);
    vector<ii> A;
    for(auto [cul, to] : a.MuchiiInactive) {
        if(a.Cul.count(cul)) {
            A.push_back({cul, to});
        }
    }
    for(auto it : A) {
        a.MuchiiInactive.erase(it);
        a.MuchiiActive.insert(it);
    }
}

struct DSU {
    int n;
    vi e;
    vector<nod> V;
    DSU(int N, vector<nod> &V0) : n(N), e(N, -1), V(V0) {}
    
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        join_nod(V[u], V[v]);
    }

    vi solve() {
        vi viz(n, 0);
        vi S;
        function<void(int)> dfs = [&](int u) {
            u = repr(u);
            if(viz[u] == 2) return;
            if(viz[u] == 1) {
                while(repr(S.back()) != repr(u)) {
                    join(u, S.back());
                    S.pop_back();
                }
                S.pop_back();
            }
            u = repr(u);
            viz[u] = 1;
            S.push_back(u);
            while(!V[u].empty()) {
                auto [cul, to] = V[u].get_muchie();
                if(repr(to) == u) continue;
                dfs(to);
                u = repr(u); /// poate au existat joinuri
            }
            if(!S.empty() && S.back() == u) 
                S.pop_back();
            viz[u] = 2;
        };
        for(int i = 0; i < n; ++i)
            if(!viz[i]) dfs(i);
        int mi = n;
        vi capat(n, 0);
        for(int i = 0; i < n; ++i) {
            if(e[i] < 0) {
                capat[i] = 1;
                for(auto [c, to] : V[i].MuchiiFol) {
                    if(repr(to) != i) {
                        capat[i] = 0;
                    }
                }
                if(capat[i]) {
                    mi = min(mi, V[i].size());
                }
            }
        }
        vi re(n, 0);
        for(int i = 0; i < n; ++i) {
            if(capat[repr(i)] && V[repr(i)].size() == mi) {
                re[i] = 1;
            }
        }
        return re;
    }
};

vi find_reachable(vi r, vi U, vi V, vi C) {
    int n = int(r.size()), m = int(U.size());
    vector<nod> V0(n);
    for(int i = 0; i < n; ++i) {
        V0[i].Noduri.insert(i);
        V0[i].Cul.insert(r[i]);
    }

    for(int i = 0; i < m; ++i) {
        V0[U[i]].add_edge(V[i], C[i]);
        V0[V[i]].add_edge(U[i], C[i]);
    }

    DSU Sol(n, V0);
    return Sol.solve();
}

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