oj.uz

Submission #75071

# Submission time Handle Problem Language Result Execution time Memory
75071 2018-09-08T08:36:00 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 636 ms 33320 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()%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 336 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 2 ms 248 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 332 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 416 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 30 ms 2636 KB Output is correct
3 Correct 407 ms 21216 KB Output is correct
4 Correct 397 ms 21236 KB Output is correct
5 Correct 440 ms 21236 KB Output is correct
6 Correct 385 ms 21232 KB Output is correct
7 Correct 397 ms 21292 KB Output is correct
8 Correct 401 ms 21224 KB Output is correct
9 Correct 392 ms 21280 KB Output is correct
10 Correct 401 ms 21280 KB Output is correct
11 Correct 395 ms 23096 KB Output is correct
12 Correct 437 ms 23596 KB Output is correct
13 Correct 410 ms 23296 KB Output is correct
14 Correct 416 ms 22468 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3236 KB Output is correct
2 Correct 76 ms 5880 KB Output is correct
3 Correct 93 ms 9596 KB Output is correct
4 Correct 263 ms 28408 KB Output is correct
5 Correct 277 ms 26632 KB Output is correct
6 Correct 248 ms 26844 KB Output is correct
7 Correct 259 ms 26896 KB Output is correct
8 Correct 261 ms 26852 KB Output is correct
9 Correct 261 ms 26660 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 2648 KB Output is correct
3 Correct 256 ms 16520 KB Output is correct
4 Correct 401 ms 21240 KB Output is correct
5 Correct 369 ms 21196 KB Output is correct
6 Correct 363 ms 21228 KB Output is correct
7 Correct 389 ms 21208 KB Output is correct
8 Correct 367 ms 21204 KB Output is correct
9 Correct 411 ms 21216 KB Output is correct
10 Correct 417 ms 21232 KB Output is correct
11 Correct 405 ms 22284 KB Output is correct
12 Correct 382 ms 22424 KB Output is correct
13 Correct 415 ms 22272 KB Output is correct
14 Correct 415 ms 23408 KB Output is correct
15 Correct 379 ms 21216 KB Output is correct
16 Correct 370 ms 21296 KB Output is correct
17 Correct 413 ms 23000 KB Output is correct
18 Correct 428 ms 22840 KB Output is correct
19 Correct 356 ms 21232 KB Output is correct
20 Correct 382 ms 24136 KB Output is correct
21 Correct 364 ms 21480 KB Output is correct
22 Correct 335 ms 21468 KB Output is correct
23 Correct 384 ms 21456 KB Output is correct
24 Correct 378 ms 22148 KB Output is correct
25 Correct 412 ms 26588 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3084 KB Output is correct
2 Correct 42 ms 3244 KB Output is correct
3 Correct 407 ms 24636 KB Output is correct
4 Correct 501 ms 27156 KB Output is correct
5 Correct 582 ms 31736 KB Output is correct
6 Correct 609 ms 31748 KB Output is correct
7 Correct 586 ms 31580 KB Output is correct
8 Correct 599 ms 31740 KB Output is correct
9 Correct 533 ms 24344 KB Output is correct
10 Correct 526 ms 24752 KB Output is correct
11 Correct 602 ms 25428 KB Output is correct
12 Correct 583 ms 30724 KB Output is correct
13 Correct 561 ms 31264 KB Output is correct
14 Correct 633 ms 33132 KB Output is correct
15 Correct 620 ms 33080 KB Output is correct
16 Correct 636 ms 28344 KB Output is correct
17 Correct 401 ms 21476 KB Output is correct
18 Correct 408 ms 21932 KB Output is correct
19 Correct 392 ms 21732 KB Output is correct
20 Correct 419 ms 21800 KB Output is correct
21 Correct 579 ms 30356 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3020 KB Output is correct
2 Correct 34 ms 3280 KB Output is correct
3 Correct 433 ms 24844 KB Output is correct
4 Correct 462 ms 25872 KB Output is correct
5 Correct 513 ms 27144 KB Output is correct
6 Correct 603 ms 31752 KB Output is correct
7 Correct 448 ms 24836 KB Output is correct
8 Correct 456 ms 25864 KB Output is correct
9 Correct 498 ms 27160 KB Output is correct
10 Correct 607 ms 31768 KB Output is correct
11 Correct 605 ms 31784 KB Output is correct
12 Correct 603 ms 31764 KB Output is correct
13 Correct 572 ms 25328 KB Output is correct
14 Correct 576 ms 24816 KB Output is correct
15 Correct 566 ms 25308 KB Output is correct
16 Correct 547 ms 24796 KB Output is correct
17 Correct 571 ms 25356 KB Output is correct
18 Correct 581 ms 24820 KB Output is correct
19 Correct 579 ms 31428 KB Output is correct
20 Correct 554 ms 32316 KB Output is correct
21 Correct 614 ms 33268 KB Output is correct
22 Correct 618 ms 33232 KB Output is correct
23 Correct 591 ms 33132 KB Output is correct
24 Correct 617 ms 33320 KB Output is correct
25 Correct 616 ms 33312 KB Output is correct
26 Correct 613 ms 33120 KB Output is correct
27 Correct 391 ms 21748 KB Output is correct
28 Correct 412 ms 21644 KB Output is correct
29 Correct 408 ms 21880 KB Output is correct
30 Correct 471 ms 21940 KB Output is correct
31 Correct 421 ms 21668 KB Output is correct
32 Correct 429 ms 21704 KB Output is correct
33 Correct 407 ms 21968 KB Output is correct
34 Correct 415 ms 21760 KB Output is correct
35 Correct 418 ms 21604 KB Output is correct
36 Correct 417 ms 21596 KB Output is correct
37 Partially correct 420 ms 22000 KB Output is partially correct
38 Correct 467 ms 22308 KB Output is correct
39 Correct 589 ms 31504 KB Output is correct
40 Correct 562 ms 31248 KB Output is correct
41 Correct 573 ms 30248 KB Output is correct
42 Correct 578 ms 30436 KB Output is correct