oj.uz

Submission #75070

# Submission time Handle Problem Language Result Execution time Memory
75070 2018-09-08T08:29:36 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 677 ms 33300 KB 
    #include "highway.h"
     
     
     
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
     
     
    mt19937 rng(56246233);
    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:78: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 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 412 KB Output is correct
6 Correct 2 ms 296 KB Output is correct
7 Correct 2 ms 376 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 336 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 5 ms 548 KB Output is correct
2 Correct 35 ms 2604 KB Output is correct
3 Correct 423 ms 21240 KB Output is correct
4 Correct 410 ms 21236 KB Output is correct
5 Correct 381 ms 21232 KB Output is correct
6 Correct 374 ms 21240 KB Output is correct
7 Correct 383 ms 21228 KB Output is correct
8 Correct 383 ms 21244 KB Output is correct
9 Correct 376 ms 21236 KB Output is correct
10 Correct 386 ms 21228 KB Output is correct
11 Correct 393 ms 23044 KB Output is correct
12 Correct 389 ms 23296 KB Output is correct
13 Correct 440 ms 23296 KB Output is correct
14 Correct 397 ms 22344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3248 KB Output is correct
2 Correct 59 ms 6560 KB Output is correct
3 Correct 81 ms 9332 KB Output is correct
4 Correct 260 ms 26832 KB Output is correct
5 Correct 254 ms 26840 KB Output is correct
6 Correct 246 ms 26544 KB Output is correct
7 Correct 277 ms 26808 KB Output is correct
8 Correct 263 ms 26536 KB Output is correct
9 Correct 255 ms 26836 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 59 ms 2676 KB Output is correct
3 Correct 282 ms 16508 KB Output is correct
4 Correct 383 ms 21228 KB Output is correct
5 Correct 386 ms 21248 KB Output is correct
6 Correct 363 ms 21220 KB Output is correct
7 Correct 352 ms 21156 KB Output is correct
8 Correct 392 ms 21276 KB Output is correct
9 Correct 395 ms 21228 KB Output is correct
10 Correct 423 ms 21316 KB Output is correct
11 Correct 428 ms 22612 KB Output is correct
12 Correct 406 ms 22440 KB Output is correct
13 Correct 413 ms 22676 KB Output is correct
14 Correct 449 ms 22604 KB Output is correct
15 Correct 361 ms 21220 KB Output is correct
16 Correct 380 ms 21180 KB Output is correct
17 Correct 418 ms 23156 KB Output is correct
18 Correct 397 ms 22684 KB Output is correct
19 Correct 405 ms 21168 KB Output is correct
20 Correct 370 ms 24144 KB Output is correct
21 Correct 374 ms 21404 KB Output is correct
22 Correct 401 ms 21408 KB Output is correct
23 Correct 352 ms 21468 KB Output is correct
24 Correct 374 ms 22136 KB Output is correct
25 Correct 442 ms 26272 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3020 KB Output is correct
2 Correct 43 ms 3268 KB Output is correct
3 Correct 477 ms 24540 KB Output is correct
4 Correct 508 ms 27200 KB Output is correct
5 Correct 613 ms 31736 KB Output is correct
6 Correct 616 ms 31748 KB Output is correct
7 Correct 587 ms 31600 KB Output is correct
8 Correct 590 ms 31736 KB Output is correct
9 Correct 554 ms 24276 KB Output is correct
10 Correct 560 ms 24828 KB Output is correct
11 Correct 600 ms 25372 KB Output is correct
12 Correct 588 ms 30716 KB Output is correct
13 Correct 598 ms 31228 KB Output is correct
14 Correct 602 ms 33244 KB Output is correct
15 Correct 627 ms 33076 KB Output is correct
16 Correct 585 ms 28372 KB Output is correct
17 Correct 418 ms 21492 KB Output is correct
18 Correct 422 ms 21824 KB Output is correct
19 Correct 491 ms 21728 KB Output is correct
20 Correct 401 ms 21812 KB Output is correct
21 Correct 561 ms 31052 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2992 KB Output is correct
2 Correct 40 ms 3272 KB Output is correct
3 Correct 420 ms 24860 KB Output is correct
4 Correct 465 ms 25968 KB Output is correct
5 Correct 481 ms 27132 KB Output is correct
6 Correct 600 ms 31744 KB Output is correct
7 Correct 460 ms 24840 KB Output is correct
8 Correct 458 ms 25896 KB Output is correct
9 Correct 509 ms 27164 KB Output is correct
10 Correct 587 ms 31740 KB Output is correct
11 Correct 596 ms 31768 KB Output is correct
12 Correct 604 ms 31720 KB Output is correct
13 Correct 559 ms 25392 KB Output is correct
14 Correct 545 ms 24876 KB Output is correct
15 Correct 666 ms 25320 KB Output is correct
16 Correct 545 ms 24792 KB Output is correct
17 Correct 594 ms 25340 KB Output is correct
18 Correct 562 ms 24784 KB Output is correct
19 Correct 573 ms 31464 KB Output is correct
20 Correct 677 ms 32372 KB Output is correct
21 Correct 619 ms 33272 KB Output is correct
22 Correct 549 ms 33240 KB Output is correct
23 Correct 611 ms 33152 KB Output is correct
24 Correct 617 ms 33300 KB Output is correct
25 Correct 655 ms 33264 KB Output is correct
26 Correct 590 ms 33120 KB Output is correct
27 Correct 410 ms 21828 KB Output is correct
28 Correct 410 ms 21720 KB Output is correct
29 Correct 428 ms 21872 KB Output is correct
30 Correct 432 ms 21952 KB Output is correct
31 Correct 428 ms 21648 KB Output is correct
32 Correct 410 ms 21592 KB Output is correct
33 Correct 435 ms 22048 KB Output is correct
34 Correct 400 ms 21732 KB Output is correct
35 Correct 422 ms 21616 KB Output is correct
36 Correct 421 ms 21616 KB Output is correct
37 Partially correct 424 ms 22008 KB Output is partially correct
38 Correct 415 ms 22392 KB Output is correct
39 Correct 581 ms 30280 KB Output is correct
40 Correct 576 ms 30580 KB Output is correct
41 Correct 560 ms 30676 KB Output is correct
42 Correct 567 ms 29964 KB Output is correct