oj.uz

Submission #75075

# Submission time Handle Problem Language Result Execution time Memory
75075 2018-09-08T08:42:53 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 695 ms 33404 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()^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

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 420 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 2 ms 248 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 424 KB Output is correct
2 Correct 56 ms 2636 KB Output is correct
3 Correct 408 ms 21224 KB Output is correct
4 Correct 402 ms 21220 KB Output is correct
5 Correct 409 ms 21300 KB Output is correct
6 Correct 386 ms 21220 KB Output is correct
7 Correct 393 ms 21228 KB Output is correct
8 Correct 363 ms 21228 KB Output is correct
9 Correct 393 ms 21224 KB Output is correct
10 Correct 400 ms 21252 KB Output is correct
11 Correct 392 ms 22760 KB Output is correct
12 Correct 425 ms 24192 KB Output is correct
13 Correct 506 ms 23312 KB Output is correct
14 Correct 491 ms 22348 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3184 KB Output is correct
2 Correct 47 ms 6556 KB Output is correct
3 Correct 73 ms 8848 KB Output is correct
4 Correct 258 ms 28324 KB Output is correct
5 Correct 264 ms 28624 KB Output is correct
6 Correct 223 ms 26844 KB Output is correct
7 Correct 223 ms 28728 KB Output is correct
8 Correct 257 ms 26536 KB Output is correct
9 Correct 226 ms 26884 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 36 ms 2652 KB Output is correct
3 Correct 254 ms 16584 KB Output is correct
4 Correct 384 ms 21232 KB Output is correct
5 Correct 376 ms 21188 KB Output is correct
6 Correct 460 ms 21232 KB Output is correct
7 Correct 374 ms 21236 KB Output is correct
8 Correct 458 ms 21216 KB Output is correct
9 Correct 401 ms 21232 KB Output is correct
10 Correct 425 ms 21240 KB Output is correct
11 Correct 400 ms 22440 KB Output is correct
12 Correct 417 ms 22580 KB Output is correct
13 Correct 433 ms 22772 KB Output is correct
14 Correct 398 ms 23492 KB Output is correct
15 Correct 369 ms 21212 KB Output is correct
16 Correct 361 ms 20896 KB Output is correct
17 Correct 404 ms 23172 KB Output is correct
18 Correct 385 ms 23032 KB Output is correct
19 Correct 389 ms 21180 KB Output is correct
20 Correct 390 ms 24380 KB Output is correct
21 Correct 411 ms 21400 KB Output is correct
22 Correct 368 ms 21408 KB Output is correct
23 Correct 372 ms 21476 KB Output is correct
24 Correct 371 ms 22128 KB Output is correct
25 Correct 427 ms 26272 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2984 KB Output is correct
2 Correct 46 ms 3272 KB Output is correct
3 Correct 483 ms 24568 KB Output is correct
4 Correct 512 ms 27172 KB Output is correct
5 Correct 644 ms 31740 KB Output is correct
6 Correct 560 ms 31740 KB Output is correct
7 Correct 586 ms 31592 KB Output is correct
8 Correct 559 ms 31716 KB Output is correct
9 Correct 524 ms 24216 KB Output is correct
10 Correct 571 ms 24812 KB Output is correct
11 Correct 606 ms 25364 KB Output is correct
12 Correct 596 ms 30744 KB Output is correct
13 Correct 623 ms 31264 KB Output is correct
14 Correct 588 ms 33136 KB Output is correct
15 Correct 599 ms 33164 KB Output is correct
16 Correct 575 ms 28344 KB Output is correct
17 Correct 388 ms 21476 KB Output is correct
18 Correct 450 ms 21728 KB Output is correct
19 Correct 424 ms 21788 KB Output is correct
20 Correct 376 ms 21804 KB Output is correct
21 Correct 589 ms 30476 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2976 KB Output is correct
2 Correct 40 ms 3268 KB Output is correct
3 Correct 436 ms 24852 KB Output is correct
4 Correct 502 ms 25920 KB Output is correct
5 Correct 631 ms 27288 KB Output is correct
6 Correct 594 ms 31744 KB Output is correct
7 Correct 464 ms 24836 KB Output is correct
8 Correct 477 ms 25880 KB Output is correct
9 Correct 507 ms 27152 KB Output is correct
10 Correct 629 ms 31732 KB Output is correct
11 Correct 579 ms 31792 KB Output is correct
12 Correct 646 ms 31760 KB Output is correct
13 Correct 560 ms 25348 KB Output is correct
14 Correct 536 ms 24732 KB Output is correct
15 Correct 641 ms 25288 KB Output is correct
16 Correct 672 ms 24916 KB Output is correct
17 Correct 695 ms 25420 KB Output is correct
18 Correct 590 ms 24856 KB Output is correct
19 Correct 602 ms 31416 KB Output is correct
20 Correct 612 ms 32368 KB Output is correct
21 Correct 626 ms 33372 KB Output is correct
22 Correct 610 ms 33264 KB Output is correct
23 Correct 621 ms 33232 KB Output is correct
24 Correct 669 ms 33320 KB Output is correct
25 Correct 645 ms 33404 KB Output is correct
26 Correct 581 ms 33104 KB Output is correct
27 Correct 399 ms 21716 KB Output is correct
28 Correct 402 ms 21652 KB Output is correct
29 Correct 432 ms 21868 KB Output is correct
30 Correct 392 ms 21972 KB Output is correct
31 Partially correct 411 ms 21664 KB Output is partially correct
32 Correct 439 ms 21588 KB Output is correct
33 Correct 401 ms 21972 KB Output is correct
34 Correct 420 ms 21724 KB Output is correct
35 Correct 413 ms 21596 KB Output is correct
36 Correct 370 ms 21684 KB Output is correct
37 Correct 421 ms 22104 KB Output is correct
38 Correct 409 ms 22276 KB Output is correct
39 Correct 575 ms 30596 KB Output is correct
40 Correct 616 ms 30360 KB Output is correct
41 Correct 579 ms 30644 KB Output is correct
42 Correct 562 ms 29964 KB Output is correct