Submission #436292

#	Time	Username	Problem	Language	Result	Execution time	Memory
436292		dacin21	Keys (IOI21_keys)	C++17	100 / 100	2487 ms	343412 KiB

keys

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") // yandex

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

uint64_t steps = 0;
uint64_t steps_2 = 0;

struct Node{
    int me = -2, next = -1;
};
// first node is sentinel
vector<Node> nodes{Node{-1, 0}};

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

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

void list_join(pair<int, int> &a, pair<int, int> b){
    // 0, 0 is invalid empty list
    if(a.first == 0 && a.second == 0){
        a = b;
        return;
    }
    nodes[a.second].next = b.first;
    a.second = b.second;
}
struct Component{
    vector<int> vertices;
    unordered_set<int> keys;
    unordered_map<int, int> edge_pos;
    // pair<first_node, last_node>
    unordered_map<int, pair<int, int> > reachable_edges;
    unordered_map<int, pair<int, int> > unreachable_edges;


    template<typename T>
    bool search(T callback){
        while(!reachable_edges.empty()){
            auto it = reachable_edges.begin();
            Node u = nodes[it->second.first];
            while(u.me != -1){
                auto p = u.me;
                auto &pos = edge_pos[p];
                auto const&vv = edge_components[p].vertices;
                while(pos < (int)vv.size()){
                    if(callback(vv[pos])) return true;
                    ++pos;
                }
                it->second.first = u.next;
                u = nodes[u.next];
            }
            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];
                list_join(v, w);
                unreachable_edges.erase(c);
            }
        }
    }
    size_t size(){
        return reachable_edges.size() + unreachable_edges.size() + keys.size() /*+edge_pos.size()*/;
    }
    void absorb(Component &o){
        join(vertices, o.vertices);
        for(auto &e:o.reachable_edges){
            ++steps;
            list_join(reachable_edges[e.first], e.second);
        }
        for(auto &e:o.unreachable_edges){
            ++steps;
            if(keys.count(e.first)){
                list_join(reachable_edges[e.first], e.second);
            } else {
                list_join(unreachable_edges[e.first], e.second);
            }
        }
        for(auto &e:o.keys){
            ++steps;
            add_key(e);
        }
        if(edge_pos.size() < o.edge_pos.size()){
            edge_pos.swap(o.edge_pos);
        }
        for(auto const&e:o.edge_pos){
            ++steps;
            auto &f = edge_pos[e.first];
            f = max(f, e.second);
        }
    }
};

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

    }
    int f(int x){
        ++steps_2;
        return p[x] < 0 ? x : p[x] = f(p[x]);
    }
    Component& c(int x){
        return comps[f(x)];
    }
    bool u(int a, int b){
        ++steps;
        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) {
    #ifdef LOCAL_RUN
    auto time_a = chrono::high_resolution_clock::now();
    #endif
    const int m = u.size();
    const int n = r.size();
    unordered_map<int, vector<int> > c_inv;
    c_inv.reserve(1<<10);
    c_inv.max_load_factor(0.25);
    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

    vector<int> vert;
    vert.reserve(n);
    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){
            ++steps;
            if(vis[u] == tim) return;
            vis[u] = tim;
            nodes.push_back(Node{tim, 0});
            list_join(uni.comps[u].unreachable_edges[e.first], make_pair(nodes.size()-1, nodes.size()-1));
            //edge_components.back().vertices.push_back(u);
            vert.push_back(u);
            for(auto const&e:g[u]){
                rec(rec, e);
            }
        };
        for(auto const&f:e.second){
            ++steps_2;
            if(vis[u[f]] <= t0){
                ++tim;
                vert.clear();
                edge_components.push_back(Edge_Component{e.first});
                rec(rec, u[f]);
                edge_components.back().vertices = vert;
            }
        }
        for(auto const&f:e.second){
            g[u[f]].pop_back();
            g[v[f]].pop_back();
        }
    }
    #ifdef LOCAL_RUN
    auto time_b = chrono::high_resolution_clock::now();
    cerr << "tmp: " << chrono::duration_cast<chrono::nanoseconds>(time_b - time_a).count()*1e-9 << "\n";
    #endif

    for(int i=0; i<n; ++i){
        uni.c(i).add_key(r[i]);
        uni.c(i).vertices.push_back(i);
    }
    #ifdef LOCAL_RUN
    auto time_c = chrono::high_resolution_clock::now();
    cerr << "go search: " << chrono::duration_cast<chrono::nanoseconds>(time_c - time_b).count()*1e-9 << "\n";;
    #endif
    pair<int, vector<int> > out(n+1, {});
    // run search
    vis.assign(n, 0);
    tim = 1;
    vector<int> to(n, -1);
    vector<int> prev(n, -1);
    for(int i=0; i<n; ++i){
        int a = uni.f(i);
        ++tim;
        if(vis[a] == 0){
            vis[a] = tim;
            prev[a] = -1;
            // 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;
                        prev[b] = a;
                        vis[b] = tim;
                        // continue search with b
                        a = b;
                        return true;
                    }
                    if(vis[b] == tim){
                        //cerr << "cycle " << a;
                        // extract cycle
                        int cnt = 0;
                        for(int c = b; c != a; c = to[c]){
                            //cerr << " " << c;
                            uni.u(a, c);
                            ++cnt;
                        }
                        //cerr << "cycle: " << cnt << "\n";
                        const int aa = uni.f(a);
                        if(prev[b] != -1){
                            assert(to[prev[b]] == b);
                            to[prev[b]] = aa;
                        }
                        prev[aa] = prev[b];
                        a = aa;
                        //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;
                    //cerr << v.size() << " : ";
                    //for(auto &e : v) cerr << e << " ";
                    //cerr << "\n";
                    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;
    }
    #ifdef LOCAL_RUN
    auto time_d = chrono::high_resolution_clock::now();
    cerr << "done: " << chrono::duration_cast<chrono::nanoseconds>(time_d - time_c).count()*1e-9 << "\n";;
    cerr << steps << "\n";
    cerr << steps_2 << "\n";
    #endif
    return ret;
}

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