oj.uz

Submission #75076

# Submission time Handle Problem Language Result Execution time Memory
75076 2018-09-08T08:47:06 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 696 ms 33316 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()^1321)%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 344 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 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 376 KB Output is correct
8 Correct 4 ms 424 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 3 ms 412 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 444 KB Output is correct
2 Correct 28 ms 2644 KB Output is correct
3 Correct 416 ms 21224 KB Output is correct
4 Correct 399 ms 21208 KB Output is correct
5 Correct 411 ms 21220 KB Output is correct
6 Correct 364 ms 21312 KB Output is correct
7 Correct 414 ms 21228 KB Output is correct
8 Correct 451 ms 21332 KB Output is correct
9 Correct 397 ms 21216 KB Output is correct
10 Correct 405 ms 21332 KB Output is correct
11 Correct 385 ms 22896 KB Output is correct
12 Correct 396 ms 24108 KB Output is correct
13 Correct 394 ms 23872 KB Output is correct
14 Correct 409 ms 22244 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3340 KB Output is correct
2 Correct 63 ms 6692 KB Output is correct
3 Correct 67 ms 9696 KB Output is correct
4 Correct 232 ms 28320 KB Output is correct
5 Correct 257 ms 26560 KB Output is correct
6 Correct 256 ms 28368 KB Output is correct
7 Correct 262 ms 27100 KB Output is correct
8 Correct 241 ms 26540 KB Output is correct
9 Correct 282 ms 27196 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 31 ms 2604 KB Output is correct
3 Correct 260 ms 16508 KB Output is correct
4 Correct 390 ms 21236 KB Output is correct
5 Correct 364 ms 21220 KB Output is correct
6 Correct 371 ms 21232 KB Output is correct
7 Correct 372 ms 21332 KB Output is correct
8 Correct 393 ms 21196 KB Output is correct
9 Correct 403 ms 21224 KB Output is correct
10 Correct 397 ms 21220 KB Output is correct
11 Correct 421 ms 22004 KB Output is correct
12 Correct 378 ms 22700 KB Output is correct
13 Correct 388 ms 22772 KB Output is correct
14 Correct 395 ms 22628 KB Output is correct
15 Correct 375 ms 21336 KB Output is correct
16 Correct 364 ms 21208 KB Output is correct
17 Correct 425 ms 23180 KB Output is correct
18 Correct 387 ms 22720 KB Output is correct
19 Correct 359 ms 21168 KB Output is correct
20 Correct 396 ms 23012 KB Output is correct
21 Correct 357 ms 21416 KB Output is correct
22 Correct 360 ms 21404 KB Output is correct
23 Correct 399 ms 21488 KB Output is correct
24 Correct 392 ms 22116 KB Output is correct
25 Correct 480 ms 28268 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3024 KB Output is correct
2 Correct 65 ms 3268 KB Output is correct
3 Correct 515 ms 24576 KB Output is correct
4 Correct 534 ms 27140 KB Output is correct
5 Correct 618 ms 31748 KB Output is correct
6 Correct 595 ms 31780 KB Output is correct
7 Correct 579 ms 31584 KB Output is correct
8 Correct 650 ms 31744 KB Output is correct
9 Correct 541 ms 24344 KB Output is correct
10 Correct 549 ms 24748 KB Output is correct
11 Correct 588 ms 25340 KB Output is correct
12 Correct 677 ms 30792 KB Output is correct
13 Correct 648 ms 31268 KB Output is correct
14 Correct 628 ms 33108 KB Output is correct
15 Correct 607 ms 33140 KB Output is correct
16 Correct 615 ms 28332 KB Output is correct
17 Correct 390 ms 21492 KB Output is correct
18 Correct 426 ms 21720 KB Output is correct
19 Correct 426 ms 21740 KB Output is correct
20 Correct 413 ms 21816 KB Output is correct
21 Correct 557 ms 30364 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2960 KB Output is correct
2 Correct 38 ms 3376 KB Output is correct
3 Correct 496 ms 24904 KB Output is correct
4 Correct 471 ms 25904 KB Output is correct
5 Correct 481 ms 27132 KB Output is correct
6 Correct 660 ms 31716 KB Output is correct
7 Correct 435 ms 24856 KB Output is correct
8 Correct 438 ms 25900 KB Output is correct
9 Correct 552 ms 27172 KB Output is correct
10 Correct 696 ms 31756 KB Output is correct
11 Correct 609 ms 31724 KB Output is correct
12 Correct 610 ms 31680 KB Output is correct
13 Correct 518 ms 25372 KB Output is correct
14 Correct 523 ms 24696 KB Output is correct
15 Correct 620 ms 25296 KB Output is correct
16 Correct 563 ms 24820 KB Output is correct
17 Correct 609 ms 25456 KB Output is correct
18 Correct 551 ms 24784 KB Output is correct
19 Correct 599 ms 31420 KB Output is correct
20 Correct 592 ms 32328 KB Output is correct
21 Correct 603 ms 33236 KB Output is correct
22 Correct 587 ms 33316 KB Output is correct
23 Correct 602 ms 33176 KB Output is correct
24 Correct 603 ms 33292 KB Output is correct
25 Correct 629 ms 33276 KB Output is correct
26 Correct 615 ms 33120 KB Output is correct
27 Correct 408 ms 21716 KB Output is correct
28 Correct 371 ms 21716 KB Output is correct
29 Correct 398 ms 22048 KB Output is correct
30 Correct 411 ms 21952 KB Output is correct
31 Partially correct 410 ms 21708 KB Output is partially correct
32 Partially correct 418 ms 21604 KB Output is partially correct
33 Correct 402 ms 21976 KB Output is correct
34 Correct 402 ms 21744 KB Output is correct
35 Correct 414 ms 21724 KB Output is correct
36 Correct 395 ms 21588 KB Output is correct
37 Correct 397 ms 22000 KB Output is correct
38 Correct 426 ms 22296 KB Output is correct
39 Correct 563 ms 31540 KB Output is correct
40 Correct 579 ms 31248 KB Output is correct
41 Correct 561 ms 30612 KB Output is correct
42 Correct 557 ms 31060 KB Output is correct