oj.uz

Submission #75077

# Submission time Handle Problem Language Result Execution time Memory
75077 2018-09-08T08:49:04 Z dacin21 Highway Tolls (IOI18_highway) C++14
100 / 100
 654 ms 33324 KB 
    #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()^17321)%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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 328 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 548 KB Output is correct
2 Correct 55 ms 2668 KB Output is correct
3 Correct 434 ms 21316 KB Output is correct
4 Correct 380 ms 21252 KB Output is correct
5 Correct 401 ms 21280 KB Output is correct
6 Correct 389 ms 21236 KB Output is correct
7 Correct 419 ms 21332 KB Output is correct
8 Correct 367 ms 21228 KB Output is correct
9 Correct 376 ms 21220 KB Output is correct
10 Correct 386 ms 21272 KB Output is correct
11 Correct 379 ms 22572 KB Output is correct
12 Correct 418 ms 23476 KB Output is correct
13 Correct 416 ms 22780 KB Output is correct
14 Correct 400 ms 22916 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3128 KB Output is correct
2 Correct 56 ms 6712 KB Output is correct
3 Correct 87 ms 8540 KB Output is correct
4 Correct 260 ms 27096 KB Output is correct
5 Correct 277 ms 26864 KB Output is correct
6 Correct 255 ms 28080 KB Output is correct
7 Correct 254 ms 28436 KB Output is correct
8 Correct 254 ms 26540 KB Output is correct
9 Correct 261 ms 28692 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 552 KB Output is correct
2 Correct 37 ms 2604 KB Output is correct
3 Correct 267 ms 16604 KB Output is correct
4 Correct 368 ms 21224 KB Output is correct
5 Correct 371 ms 21232 KB Output is correct
6 Correct 422 ms 21220 KB Output is correct
7 Correct 375 ms 21216 KB Output is correct
8 Correct 361 ms 21204 KB Output is correct
9 Correct 414 ms 21248 KB Output is correct
10 Correct 415 ms 21220 KB Output is correct
11 Correct 385 ms 22240 KB Output is correct
12 Correct 393 ms 22436 KB Output is correct
13 Correct 397 ms 23656 KB Output is correct
14 Correct 380 ms 22308 KB Output is correct
15 Correct 386 ms 21228 KB Output is correct
16 Correct 364 ms 20880 KB Output is correct
17 Correct 395 ms 22440 KB Output is correct
18 Correct 376 ms 23428 KB Output is correct
19 Correct 381 ms 21232 KB Output is correct
20 Correct 428 ms 24356 KB Output is correct
21 Correct 392 ms 21424 KB Output is correct
22 Correct 379 ms 21380 KB Output is correct
23 Correct 384 ms 21476 KB Output is correct
24 Correct 371 ms 22136 KB Output is correct
25 Correct 476 ms 28276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2988 KB Output is correct
2 Correct 34 ms 3288 KB Output is correct
3 Correct 455 ms 24532 KB Output is correct
4 Correct 495 ms 27192 KB Output is correct
5 Correct 629 ms 31736 KB Output is correct
6 Correct 582 ms 31768 KB Output is correct
7 Correct 618 ms 31604 KB Output is correct
8 Correct 608 ms 31760 KB Output is correct
9 Correct 492 ms 24284 KB Output is correct
10 Correct 566 ms 24924 KB Output is correct
11 Correct 574 ms 25348 KB Output is correct
12 Correct 567 ms 30724 KB Output is correct
13 Correct 600 ms 31236 KB Output is correct
14 Correct 606 ms 33120 KB Output is correct
15 Correct 654 ms 33156 KB Output is correct
16 Correct 603 ms 28376 KB Output is correct
17 Correct 378 ms 21488 KB Output is correct
18 Correct 397 ms 21788 KB Output is correct
19 Correct 431 ms 21836 KB Output is correct
20 Correct 393 ms 21788 KB Output is correct
21 Correct 572 ms 30368 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3128 KB Output is correct
2 Correct 47 ms 3236 KB Output is correct
3 Correct 432 ms 24864 KB Output is correct
4 Correct 486 ms 26008 KB Output is correct
5 Correct 504 ms 27136 KB Output is correct
6 Correct 576 ms 31736 KB Output is correct
7 Correct 454 ms 24856 KB Output is correct
8 Correct 451 ms 25992 KB Output is correct
9 Correct 519 ms 27180 KB Output is correct
10 Correct 616 ms 31740 KB Output is correct
11 Correct 615 ms 31728 KB Output is correct
12 Correct 611 ms 31736 KB Output is correct
13 Correct 532 ms 25368 KB Output is correct
14 Correct 549 ms 24792 KB Output is correct
15 Correct 586 ms 25356 KB Output is correct
16 Correct 555 ms 24776 KB Output is correct
17 Correct 589 ms 25344 KB Output is correct
18 Correct 590 ms 24880 KB Output is correct
19 Correct 584 ms 31440 KB Output is correct
20 Correct 595 ms 32324 KB Output is correct
21 Correct 636 ms 33244 KB Output is correct
22 Correct 624 ms 33244 KB Output is correct
23 Correct 617 ms 33132 KB Output is correct
24 Correct 622 ms 33320 KB Output is correct
25 Correct 617 ms 33324 KB Output is correct
26 Correct 607 ms 33116 KB Output is correct
27 Correct 384 ms 21732 KB Output is correct
28 Correct 415 ms 21776 KB Output is correct
29 Correct 423 ms 21876 KB Output is correct
30 Correct 414 ms 22056 KB Output is correct
31 Correct 421 ms 21664 KB Output is correct
32 Correct 418 ms 21616 KB Output is correct
33 Correct 446 ms 21964 KB Output is correct
34 Correct 395 ms 21828 KB Output is correct
35 Correct 444 ms 21592 KB Output is correct
36 Correct 396 ms 21644 KB Output is correct
37 Correct 433 ms 22004 KB Output is correct
38 Correct 471 ms 22308 KB Output is correct
39 Correct 558 ms 31504 KB Output is correct
40 Correct 557 ms 30232 KB Output is correct
41 Correct 562 ms 30992 KB Output is correct
42 Correct 544 ms 29956 KB Output is correct