Submission #439420

#	Time	Username	Problem	Language	Result	Execution time	Memory
439420		dacin21	Keys (IOI21_keys)	C++17	9 / 100	910 ms	159904 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;


template<typename Key, typename Value>
class Mergeable_Map{
    struct Node{
        Node *l, *r;
        Key key;
        Value value;
    };
    static constexpr Key key_min(){
        return numeric_limits<Key>::min();
    }
    static constexpr Key key_max(){
        return numeric_limits<Key>::max();
    }
    static Key key_middle(Key const&l, Key const&r){
        return l + ((r>>1)-(l>>1));
    }

    template<typename Fun>
    void foreach_rec(Node*u, Key a, Key b, Fun const&fun){
        fun((Key const&)u->key, u->value);
        const Key m = key_middle(a, b);
        if(u->l) foreach_rec(u->l, a, m, fun);
        if(u->r) foreach_rec(u->r, m+1, b, fun);
    }
    template<typename Fun>
    Node* merge_rec(Node*u, Node*v, Key a, Key b, Fun const&merge_fun){
        if(!u) return v;
        if(!v) return u;
        //cerr << "merge " << a << " " << b << " " << root_size << "\n";
        const int m = key_middle(a, b);
        if(v->l) u->l = merge_rec(u->l, v->l, a, m, merge_fun);
        if(v->r) u->r = merge_rec(u->r, v->r, m+1, b, merge_fun);
        v->l = v->r = nullptr;
        if(u->key == v->key){
            --root_size;
            merge_fun(u->value, v->value);
            delete v;
            return u;
        }
        if(u->key > v->key){
            swap(u->key, v->key);
            swap(u->value, v->value);
        }
        if(v->key <= m){
            u->l = merge_rec(u->l, v, a, m, merge_fun);
        } else {
            u->r = merge_rec(u->r, v, m+1, b, merge_fun);
        }
        return u;
    }
    template<bool find_only>
    Node* find_or_emplace(Key x, Value v){
        auto construct_new_node = [&]() -> Node*{
            if(find_only) return nullptr;
            ++root_size;
            return new Node{nullptr, nullptr, x, v};
        };
        if(!root){
            return root = construct_new_node();
        }
        Node* ret = nullptr;
        Node*u = root;
        Key a = key_min();
        Key b = key_max();
        for(;;){
            assert(u);
            if(x < u->key){
                if(find_only){
                    return nullptr;
                }
                swap(x, u->key);
                swap(v, u->value);
                if(!ret) ret = u; // we now insert an old value -> save u in ret
            } else if(x == u->key){
                return u;
            }
            const Key m = key_middle(a, b);
            if(x <= m){
                if(!u->l){
                    u->l = construct_new_node();
                    return ret ? ret : u->l;
                }
                b = m;
                u = u->l;
            } else {
                if(!u->r){
                    u->r = construct_new_node();
                    return ret ? ret : u->r;
                }
                a = m+1;
                u = u->r;
            }
        }
    }
    struct merge_with_plus{
        template<typename T>
        void operator()(T &a, T const&b){
            a += b;
        }
    };
    void erase_back_rec(){
        --root_size;
        Node** uu = &root;
        Node*u = root;
        for(;;){
            if(u->r){
                uu = &(u->r);
                u = u->r;
            } else if(u->l){
                uu = &(u->l);
                u = u->l;
            } else {
                delete u;
                *uu = nullptr;
                break;
            }
        }
    }
    void erase_front_rec(){
        --root_size;
        Node** uu = &root;
        Node*u = root;
        for(;;){
            if(u->l){
                swap(u->key, u->l->key);
                swap(u->value, u->l->value);
                uu = &(u->l);
                u = u->l;
            } else if(u->r){
                swap(u->key, u->r->key);
                swap(u->value, u->r->value);
                uu = &(u->r);
                u = u->r;
            } else {
                delete u;
                *uu = nullptr;
                break;
            }
        }
    }
    void erase_rec(Key const&x){
        --root_size;
        Node** uu = &root;
        Node*u = root;
        Key a = key_min();
        Key b = key_max();
        while(u->key != x){
            auto const m = key_middle(a, b);
            if(x <= m){
                uu = &(u->l);
                u = u->l;
                b = m;
            } else {
                uu = &(u->r);
                u = u->r;
                a = m+1;
            }
        }
        for(;;){
            if(u->l){
                swap(u->key, u->l->key);
                swap(u->value, u->l->value);
                uu = &(u->l);
                u = u->l;
            } else if(u->r) {
                swap(u->key, u->r->key);
                swap(u->value, u->r->value);
                uu = &(u->r);
                u = u->r;
            } else {
                delete u;
                *uu = nullptr;
                break;
            }
        }
    }

public:
    bool empty(){
        return !root;
    }
    size_t size(){
        return root_size;
    }

    pair<Key&, Value&> back(){
        assert(!empty());
        Node*u = root;
        while(u->r) u = u->r;
        return {u->key, u->value};
    }
    void pop_back(){
        erase_back_rec();
    }
    pair<Key&, Value&> front(){
        assert(!empty());
        return {root->key, root->value};
    }
    void pop_front(){
        erase_front_rec();
    }

    int count(Key const&x){
        Node*u = find_or_emplace<true>(x, Value{});
        return !!u;
    }
    Value& operator[](Key const&x){
        Node*u = find_or_emplace<false>(x, Value{});
        return u->value;
    }
    void erase(Key const&x){
        erase_rec(x);
    }

    template<typename Fun>
    void absorb(Mergeable_Map &o, Fun merge_fun = merge_with_plus{}){
        root_size += o.root_size;
        root = merge_rec(root, o.root, key_min(), key_max(), merge_fun);
        o.root_size = 0;
        o.root = nullptr;
    }
    template<typename Fun>
    void foreach(Fun fun){
        if(root){
            foreach_rec(root, key_min(), key_max(), fun);
        }
    }
private:
    size_t root_size = 0;
    Node *root = nullptr;
};

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()){
        a.swap(b);
    }
    steps_2 += b.size();
    a.insert(a.end(), b.begin(), b.end());
    b.clear();
}


struct Component{
    vector<int> vertices;
    unordered_set<int> keys;
    Mergeable_Map<int, int> edge_pos;
    Mergeable_Map<int, vector<int> > reachable_edges;
    Mergeable_Map<int, vector<int> > unreachable_edges;
    //map<int, vector<int> > unreachable_edges;


    template<typename T>
    bool search(T callback){
        while(!reachable_edges.empty()){
            auto it = reachable_edges.back();
            while(!it.second.empty()){
                auto&p = it.second.back();
                auto &pos = edge_pos[p];
                auto&vv = edge_components[p].vertices;
                while(pos < (int)vv.size()){
                    if(callback(vv[pos])) return true;
                    ++pos;
                }
                it.second.pop_back();
            }
            reachable_edges.pop_back();
        }
        return false;
    }
    void add_key(int c){
        if(!keys.count(c)){
            keys.insert(c);
            //cerr << "add key " << c << "\n";
            if(unreachable_edges.count(c)){
                auto &v = reachable_edges[c];
                auto &w = unreachable_edges[c];
                //cerr << v.size() << " " << w.size() << "\n";
                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);
        o.reachable_edges.foreach([&](auto const& first, auto & second){
            ++steps;
            join(reachable_edges[first], second);
        });
        //cerr << "absorb " << unreachable_edges.size() << " " << reachable_edges.size() << " " << o.unreachable_edges.size() << "\n";
        /*for(auto &e:o.unreachable_edges){
            ++steps;
            if(keys.count(e.first)){
                join(reachable_edges[e.first], e.second);
            } else {
                join(unreachable_edges[e.first], e.second);
            }
        }*/
        o.unreachable_edges.foreach([&](auto const&first, auto &second){
            ++steps;
            if(keys.count(first)){
                join(reachable_edges[first], second);
                second.clear();
            }
        });
        unreachable_edges.absorb(o.unreachable_edges, join<int>);
        for(auto &e:o.keys){
            ++steps;
            add_key(e);
        }
        //cerr << " -> " << unreachable_edges.size() << " " << reachable_edges.size() << "\n";
        edge_pos.absorb(o.edge_pos, [&](auto const&a, auto const&b){ return max(a, b); });
    }
};

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;
            //cerr << "add unreachable " << u << " " << e.first << "\n";
            uni.comps[u].unreachable_edges[e.first].push_back(tim);
            //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_Compoment{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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33