제출 #1063098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063098		vjudge1	열쇠 (IOI21_keys)	C++17	67 / 100	3088 ms	277760 KiB

keys

#include <bits/stdc++.h>

using namespace std;

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

struct nod {
    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;
    }


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

template<class T>
void merge(set<T> &a, set<T> &b) {
    if(a.size() < b.size()) swap(a, b);
    for(auto it : b)
        a.insert(it);
}

void join_nod(nod &a, nod &b) {
    ///va pune info din b in a
    merge(a.Cul, b.Cul);
    merge(a.MuchiiFol, b.MuchiiFol);
    merge(a.MuchiiActive, b.MuchiiActive);
    merge(a.MuchiiInactive, b.MuchiiInactive);
   // for(auto it : b.MuchiiInactive)
   //     a.MuchiiInactive.insert(it);
    for(auto c : a.Cul) {
        while(1) {
            auto it = a.MuchiiInactive.lower_bound(ii{c, -1});
            if(it == a.MuchiiInactive.end() || it->first != c) break;
            auto v = *it;
            a.MuchiiInactive.erase(v);
            a.MuchiiActive.insert(v);
        }
    }
}

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, -e[i]);
                }
            }
        }
        vi re(n, 0);
        for(int i = 0; i < n; ++i) {
            if(capat[repr(i)] && -e[repr(i)] == 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].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: 30 / 30
• Subtask 5: 0 / 33