oj.uz

Submission #75074

# Submission time Handle Problem Language Result Execution time Memory
75074 2018-09-08T08:40:58 Z dacin21 Highway Tolls (IOI18_highway) C++14
100 / 100
 685 ms 33284 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()^9)%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 376 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 6 ms 420 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 2 ms 252 KB Output is correct
12 Correct 2 ms 416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 464 KB Output is correct
2 Correct 47 ms 2648 KB Output is correct
3 Correct 412 ms 21232 KB Output is correct
4 Correct 384 ms 21216 KB Output is correct
5 Correct 401 ms 21220 KB Output is correct
6 Correct 390 ms 21216 KB Output is correct
7 Correct 394 ms 21232 KB Output is correct
8 Correct 375 ms 21232 KB Output is correct
9 Correct 402 ms 21240 KB Output is correct
10 Correct 404 ms 21236 KB Output is correct
11 Correct 391 ms 22832 KB Output is correct
12 Correct 385 ms 23312 KB Output is correct
13 Correct 397 ms 23872 KB Output is correct
14 Correct 406 ms 22396 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3456 KB Output is correct
2 Correct 54 ms 6496 KB Output is correct
3 Correct 86 ms 9348 KB Output is correct
4 Correct 277 ms 28708 KB Output is correct
5 Correct 262 ms 28728 KB Output is correct
6 Correct 243 ms 28076 KB Output is correct
7 Correct 251 ms 26640 KB Output is correct
8 Correct 233 ms 26544 KB Output is correct
9 Correct 262 ms 26552 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 35 ms 2636 KB Output is correct
3 Correct 274 ms 16580 KB Output is correct
4 Correct 405 ms 21216 KB Output is correct
5 Correct 369 ms 21224 KB Output is correct
6 Correct 401 ms 21232 KB Output is correct
7 Correct 483 ms 21208 KB Output is correct
8 Correct 405 ms 21188 KB Output is correct
9 Correct 416 ms 21224 KB Output is correct
10 Correct 410 ms 21232 KB Output is correct
11 Correct 444 ms 22484 KB Output is correct
12 Correct 403 ms 22564 KB Output is correct
13 Correct 423 ms 22720 KB Output is correct
14 Correct 402 ms 22356 KB Output is correct
15 Correct 373 ms 21216 KB Output is correct
16 Correct 359 ms 20892 KB Output is correct
17 Correct 400 ms 22468 KB Output is correct
18 Correct 386 ms 22856 KB Output is correct
19 Correct 377 ms 21236 KB Output is correct
20 Correct 406 ms 23280 KB Output is correct
21 Correct 376 ms 21484 KB Output is correct
22 Correct 342 ms 21396 KB Output is correct
23 Correct 355 ms 21452 KB Output is correct
24 Correct 434 ms 22172 KB Output is correct
25 Correct 431 ms 28276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3024 KB Output is correct
2 Correct 93 ms 3280 KB Output is correct
3 Correct 477 ms 24540 KB Output is correct
4 Correct 513 ms 27180 KB Output is correct
5 Correct 635 ms 31832 KB Output is correct
6 Correct 606 ms 31752 KB Output is correct
7 Correct 608 ms 31564 KB Output is correct
8 Correct 608 ms 31752 KB Output is correct
9 Correct 528 ms 24340 KB Output is correct
10 Correct 575 ms 24752 KB Output is correct
11 Correct 649 ms 25344 KB Output is correct
12 Correct 578 ms 30732 KB Output is correct
13 Correct 587 ms 31240 KB Output is correct
14 Correct 611 ms 33140 KB Output is correct
15 Correct 610 ms 33104 KB Output is correct
16 Correct 592 ms 28336 KB Output is correct
17 Correct 417 ms 21472 KB Output is correct
18 Correct 415 ms 21744 KB Output is correct
19 Correct 401 ms 21756 KB Output is correct
20 Correct 429 ms 21892 KB Output is correct
21 Correct 583 ms 30452 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2984 KB Output is correct
2 Correct 43 ms 3180 KB Output is correct
3 Correct 461 ms 24852 KB Output is correct
4 Correct 495 ms 25928 KB Output is correct
5 Correct 512 ms 27112 KB Output is correct
6 Correct 635 ms 31704 KB Output is correct
7 Correct 453 ms 24816 KB Output is correct
8 Correct 462 ms 25872 KB Output is correct
9 Correct 507 ms 27164 KB Output is correct
10 Correct 596 ms 31768 KB Output is correct
11 Correct 623 ms 31708 KB Output is correct
12 Correct 633 ms 31804 KB Output is correct
13 Correct 512 ms 25512 KB Output is correct
14 Correct 538 ms 24824 KB Output is correct
15 Correct 574 ms 25348 KB Output is correct
16 Correct 570 ms 24736 KB Output is correct
17 Correct 606 ms 25352 KB Output is correct
18 Correct 565 ms 24708 KB Output is correct
19 Correct 570 ms 31424 KB Output is correct
20 Correct 547 ms 32316 KB Output is correct
21 Correct 685 ms 33224 KB Output is correct
22 Correct 605 ms 33240 KB Output is correct
23 Correct 594 ms 33132 KB Output is correct
24 Correct 627 ms 33284 KB Output is correct
25 Correct 653 ms 33276 KB Output is correct
26 Correct 608 ms 33120 KB Output is correct
27 Correct 395 ms 21724 KB Output is correct
28 Correct 425 ms 21656 KB Output is correct
29 Correct 416 ms 21908 KB Output is correct
30 Correct 404 ms 21956 KB Output is correct
31 Correct 422 ms 21668 KB Output is correct
32 Correct 445 ms 21608 KB Output is correct
33 Correct 411 ms 21980 KB Output is correct
34 Correct 406 ms 21744 KB Output is correct
35 Correct 413 ms 21604 KB Output is correct
36 Correct 402 ms 21584 KB Output is correct
37 Correct 435 ms 22004 KB Output is correct
38 Correct 439 ms 22332 KB Output is correct
39 Correct 620 ms 31580 KB Output is correct
40 Correct 607 ms 31236 KB Output is correct
41 Correct 557 ms 30684 KB Output is correct
42 Correct 570 ms 30148 KB Output is correct