제출 #436082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436082		dacin21	열쇠 (IOI21_keys)	C++17	20 / 100	2608 ms	123520 KiB

keys

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


struct Edge_Compoment{
    int key;
    vector<int> vertices;
};
vector<Edge_Compoment> edge_components;

template<typename T>
void join(vector<T> &a, vector<T> &b){
    if(a.size() < b.size()){
        swap(a, b);
    }
    a.insert(a.end(), b.begin(), b.end());
    b.clear();
}

struct Component{
    struct PP{
        int name;
        int pos;
    };
    vector<int> vertices;
    unordered_set<int> keys;
    unordered_map<int, vector<PP> > reachable_edges;
    unordered_map<int, vector<PP> > unreachable_edges;


    template<typename T>
    bool search(T callback){
        while(!reachable_edges.empty()){
            auto it = reachable_edges.begin();
            while(!it->second.empty()){
                auto&p = it->second.back();
                auto&vv = edge_components[p.name].vertices;
                while(p.pos < (int)vv.size()){
                    if(callback(vv[p.pos])) return true;
                    ++p.pos;
                }
                it->second.pop_back();
            }
            reachable_edges.erase(it);
        }
        return false;
    }
    void add_key(int c){
        if(!keys.count(c)){
            keys.insert(c);
            if(unreachable_edges.count(c)){
                auto &v = reachable_edges[c];
                auto &w = unreachable_edges[c];
                v.insert(v.end(), w.begin(), w.end());
                unreachable_edges.erase(c);
            }
        }
    }
    size_t size(){
        return reachable_edges.size() + keys.size() + vertices.size();
    }
    void absorb(Component &o){
        join(vertices, o.vertices);
        for(auto &e:o.reachable_edges){
            join(reachable_edges[e.first], e.second);
        }
        for(auto &e:o.unreachable_edges){
            join(unreachable_edges[e.first], e.second);
        }
        for(auto &e:o.keys){
            add_key(e);
        }
    }
};

struct DSU{
    DSU(int n_) : n(n_), p(n, -1), comps(n){

    }
    int f(int x){
        return p[x] < 0 ? x : f(p[x]);
    }
    Component& c(int x){
        return comps[f(x)];
    }
    bool u(int a, int b){
        a = f(a);
        b = f(b);
        if(a == b) return false;
        if(comps[a].size() < comps[b].size()){
            swap(a, b);
        }
        comps[a].absorb(comps[b]);
        p[b] = a;
        return true;
    }

    int n;
    vector<int> p;
    vector<Component> comps;

};

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

    DSU uni(n);
    // find edge components
    edge_components.clear();
    vector<vector<int> > g(n);
    vector<int> vis(n, -1);
    int tim = -1; // = index of last edge_component

    for(auto const&e:c_inv){
        for(auto const&f:e.second){
            g[u[f]].push_back(v[f]);
            g[v[f]].push_back(u[f]);
        }
        const int t0 = tim;
        auto rec = [&](auto rec, int u){
            if(vis[u] == tim) return;
            vis[u] = tim;
            uni.comps[u].unreachable_edges[e.first].push_back({tim, 0});
            edge_components.back().vertices.push_back(u);
            for(auto const&e:g[u]){
                rec(rec, e);
            }
        };
        for(auto const&f:e.second){
            if(vis[u[f]] <= t0){
                ++tim;
                edge_components.push_back(Edge_Compoment{e.first});
                rec(rec, u[f]);
            }
        }
        for(auto const&f:e.second){
            g[u[f]].pop_back();
            g[v[f]].pop_back();
        }
    }
    for(int i=0; i<n; ++i){
        uni.c(i).add_key(r[i]);
        uni.c(i).vertices.push_back(i);
    }
    pair<int, vector<int> > out(n+1, {});
    // run search
    vis.assign(n, 0);
    tim = 1;
    vector<int> to(n, -1);
    for(int i=0; i<n; ++i){
        int a = uni.f(i);
        ++tim;
        if(vis[a] == 0){
            vis[a] = tim;
            // find out edge
            for(;;){
                auto res = uni.comps[a].search([&](int const&v){
                    //cerr << " => " << v << "\n";
                    const int b = uni.f(v);
                    if(b == a) return false; // loop
                    if(vis[b] == 0){
                        //cerr << "move to: " << b << "\n";
                        to[a] = b;
                        vis[b] = tim;
                        // continue search with b
                        a = b;
                        return true;
                    }
                    if(vis[b] == tim){
                        //cerr << "cycle " << a;
                        // extract cycle
                        for(int c = b; c != a; c = to[c]){
                            //cerr << " " << c;
                            uni.u(a, c);
                        }
                        a = uni.f(a);
                        //cerr << " -> " << a << "\n";
                        to[a] = -1;
                        assert(vis[a] == tim);
                        return true;
                    }
                    // found old vertices -> finish
                    //cerr << "old " << b << "\n";
                    a = -1;
                    return true;
                });
                if(a == -1) break; // found old vertices
                if(!res){
                    auto const&v = uni.comps[a].vertices;
                    if((int)v.size() < out.first){
                        out.first = v.size();
                        out.second.clear();
                    }
                    if((int)v.size() == out.first){
                        out.second.insert(out.second.end(), v.begin(), v.end());
                    }
                    break;
                }
            }

        }
    }
    vector<int> ret(n);
    for(auto const&e:out.second){
        ret[e] = 1;
    }
    return ret;
}

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