Submission #75075

#	Time	Username	Problem	Language	Result	Execution time	Memory
75075		dacin21	Highway Tolls (IOI18_highway)	C++14	90 / 100	695 ms	33404 KiB

highway

    #include "highway.h"
     
     
     
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
     
    
array<int, 5> seeds = {409887653, 59456231, 56246231, 56246233, 931621953}; 
    mt19937 rng(seeds[(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()^13)%seeds.size()]);
    int get_rand(int l, int r){
        return uniform_int_distribution<int>(l, r)(rng);
    }
     
    int A, B, C, M, n;
    ll initial;
    int path_len;
    int ed;
    vector<vector<pair<int, int> > > g;
    map<pair<int, int>, int> deco;
     
     
     
    vector<char> state;
    vector<int> gord;
     
    bool rec(int u, int p, int pared){
        assert(state[u] == 0);
        state[u] = 1;
        int pool = -1;
        auto add_cand = [&](int e){
            if(pool == -1){
                pool = e;
            } else {
                gord.push_back(pool);
                gord.push_back(e);
                pool = -1;
            }
        };
        for(auto const&e:g[u]){
            if(e.first == p) continue;
            if(state[e.first] == 0){
                bool did = rec(e.first, u, e.second);
                if(!did){
                    add_cand(e.second);
                }
            } else if(state[e.first] == 1){
                add_cand(e.second);
            }
        }
        state[u] = 2;
        if(pool != -1){
            gord.push_back(pool);
            gord.push_back(pared);
            return true;
        }
        return false;
    }
     
    vector<int> line_graph_allign(){
        state.assign(n, 0);
        gord.clear();
     
        rec(get_rand(0, n-1), -1, -1);
     
        if(M%2){
            assert(gord.back() == -1);
            gord.pop_back();
            gord.push_back(gord.back());
        }
     
        return gord;
    }
     
     
    int find_vertex(int M, vector<int> const&U, vector<int> const&V){
        vector<int> ord = line_graph_allign();
        for(int i=0;i<ord.size();i+=2){
            int j = 2*get_rand(0, i/2);
            swap(ord[i], ord[i-j]);
            swap(ord[i+1], ord[i-j+1]);
        }
        /*for(int i=0;i<ord.size();i+=2){
            cerr << U[ord[i]] << " " << V[i] << " | " << U[i+1] << " " << V[i+1] << "\n";
        }*/
        int l = -1, r = (M+1)/2-1;
        while(l+1 < r){
            int m = l + (r-l)/2;
     
            vector<int> v(M, 1);
            for(int i=0;i/2<=m;++i) v[ord[i]] = 0;
            ll mid = ask(v);
            if(mid == path_len*(ll)A){
                r = m;
            } else {
                l = m;
            }
        }
        map<int, int> cnt;
        for(auto const&e:{U, V}){
            for(auto const&i:{ord[2*r], ord[2*r+1]}){
                ++cnt[e[i]];
            }
        }
        for(auto const&e:cnt){
            if(e.second == 2){
                return e.first;
            }
        }
        assert(0);
        return -1;
     
    }
    int far_search(int u, vector<int> const&U, vector<int> const&V, bool fix_d){
        vector<int> ord, vis(n, 0);
        vector<int> inv_ord(n);
        vector<int> d;
        ord.push_back(u);
        d.push_back(0);
        vis[u] = 1;
        for(int i=0;i<(int)ord.size();++i){
            int v = ord[i];
            inv_ord[v] = i;
            for(auto const&f:g[v]){
                auto const e = f.first;
                if(!vis[e]){
                    vis[e] = 1;
                    ord.push_back(e);
                    d.push_back(d[i]+1);
                }
            }
        }
        assert((int)ord.size() == n);
        int l = 0, r = n;
        if(fix_d){
            l = lower_bound(d.begin(), d.end(), path_len) - d.begin();
            r = upper_bound(d.begin(), d.end(), path_len) - d.begin();
        }
        while(l+1 < r){
            int m = l + (r-l)/2;
            vector<int> v(M, 1);
            for(int i=0;i<M;++i){
                if(inv_ord[U[i]] < m && inv_ord[V[i]] < m){
                    v[i] = 0;
                }
            }
            ll dist = ask(v);
            if(dist == path_len * (ll) A){
                r = m;
            } else {
                l = m;
            }
        }
        return ord[l];
    }
     
     
    void find_pair(int N, vector<int> U, vector<int> V, int A_, int B_) {
        n=N; A=A_; B=B_;
        C = B-A;
        M = U.size();
        for(int i=0;i<M;++i){
            deco[make_pair(U[i], V[i])] = i;
            deco[make_pair(V[i], U[i])] = i;
        }
        initial = ask(vector<int>(M, 1));
        assert(initial % B == 0);
        path_len = initial / B;
        //if(path_len <= 2) ask(vector<int>(M, 1));
        g.assign(N, vector<pair<int, int> >());
        for(int i=0;i<M;++i){
            g[U[i]].emplace_back(V[i], i);
            g[V[i]].emplace_back(U[i], i);
        }
        for(auto &e:g) shuffle(e.begin(), e.end(), rng);
     
        int start = find_vertex(M, U, V);
        //cerr << "ed " << ed << " : " << U[ed] << " " << V[ed] << "\n";
        const int S = far_search(start, U, V, false);
        const int T = far_search(S, U, V, true);
        answer(S, T);
    }

Compilation message (stderr)

highway.cpp: In function 'int find_vertex(int, const std::vector<int>&, const std::vector<int>&)':
highway.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ord.size();i+=2){
                     ~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 21 / 31