oj.uz

Submission #75080

# Submission time Handle Problem Language Result Execution time Memory
75080 2018-09-08T08:56:17 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 664 ms 33308 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()^43212)%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 296 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 328 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 340 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 5 ms 536 KB Output is correct
2 Correct 50 ms 2672 KB Output is correct
3 Correct 438 ms 21236 KB Output is correct
4 Correct 394 ms 21244 KB Output is correct
5 Correct 409 ms 21244 KB Output is correct
6 Correct 381 ms 21224 KB Output is correct
7 Correct 404 ms 21272 KB Output is correct
8 Correct 391 ms 21232 KB Output is correct
9 Correct 374 ms 21236 KB Output is correct
10 Correct 419 ms 21276 KB Output is correct
11 Correct 402 ms 22840 KB Output is correct
12 Correct 417 ms 23540 KB Output is correct
13 Correct 410 ms 23888 KB Output is correct
14 Correct 392 ms 22400 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3164 KB Output is correct
2 Correct 55 ms 6532 KB Output is correct
3 Correct 79 ms 8856 KB Output is correct
4 Correct 263 ms 27020 KB Output is correct
5 Correct 272 ms 28440 KB Output is correct
6 Correct 253 ms 26304 KB Output is correct
7 Correct 274 ms 26636 KB Output is correct
8 Correct 223 ms 28080 KB Output is correct
9 Correct 257 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 2680 KB Output is correct
3 Correct 273 ms 16668 KB Output is correct
4 Correct 383 ms 21252 KB Output is correct
5 Correct 368 ms 21328 KB Output is correct
6 Correct 369 ms 21220 KB Output is correct
7 Correct 372 ms 21232 KB Output is correct
8 Correct 370 ms 21212 KB Output is correct
9 Correct 406 ms 21232 KB Output is correct
10 Correct 405 ms 21248 KB Output is correct
11 Correct 413 ms 22304 KB Output is correct
12 Correct 410 ms 22828 KB Output is correct
13 Correct 393 ms 23384 KB Output is correct
14 Correct 395 ms 23452 KB Output is correct
15 Correct 345 ms 21232 KB Output is correct
16 Correct 355 ms 20968 KB Output is correct
17 Correct 399 ms 23188 KB Output is correct
18 Correct 378 ms 23476 KB Output is correct
19 Correct 374 ms 21232 KB Output is correct
20 Correct 441 ms 22960 KB Output is correct
21 Correct 378 ms 21412 KB Output is correct
22 Correct 348 ms 21408 KB Output is correct
23 Correct 374 ms 21596 KB Output is correct
24 Correct 352 ms 22132 KB Output is correct
25 Correct 480 ms 28272 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2968 KB Output is correct
2 Correct 53 ms 3236 KB Output is correct
3 Correct 471 ms 24652 KB Output is correct
4 Correct 497 ms 27224 KB Output is correct
5 Correct 601 ms 31772 KB Output is correct
6 Correct 610 ms 31748 KB Output is correct
7 Correct 607 ms 31684 KB Output is correct
8 Correct 561 ms 31748 KB Output is correct
9 Correct 512 ms 24344 KB Output is correct
10 Correct 584 ms 24876 KB Output is correct
11 Correct 580 ms 25428 KB Output is correct
12 Correct 565 ms 30708 KB Output is correct
13 Correct 623 ms 31228 KB Output is correct
14 Correct 664 ms 33136 KB Output is correct
15 Correct 528 ms 33108 KB Output is correct
16 Correct 564 ms 28436 KB Output is correct
17 Correct 385 ms 21468 KB Output is correct
18 Correct 385 ms 21956 KB Output is correct
19 Correct 407 ms 21772 KB Output is correct
20 Correct 399 ms 21800 KB Output is correct
21 Correct 572 ms 30560 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3000 KB Output is correct
2 Correct 45 ms 3220 KB Output is correct
3 Correct 434 ms 24856 KB Output is correct
4 Correct 496 ms 25868 KB Output is correct
5 Correct 515 ms 27196 KB Output is correct
6 Correct 625 ms 31740 KB Output is correct
7 Correct 447 ms 24844 KB Output is correct
8 Correct 463 ms 26032 KB Output is correct
9 Correct 482 ms 27144 KB Output is correct
10 Correct 580 ms 31744 KB Output is correct
11 Correct 613 ms 31768 KB Output is correct
12 Correct 630 ms 31732 KB Output is correct
13 Correct 566 ms 25344 KB Output is correct
14 Correct 565 ms 24800 KB Output is correct
15 Correct 592 ms 25260 KB Output is correct
16 Correct 564 ms 24820 KB Output is correct
17 Correct 599 ms 25432 KB Output is correct
18 Correct 566 ms 24892 KB Output is correct
19 Correct 605 ms 31448 KB Output is correct
20 Correct 598 ms 32396 KB Output is correct
21 Correct 596 ms 33268 KB Output is correct
22 Correct 616 ms 33232 KB Output is correct
23 Correct 618 ms 33180 KB Output is correct
24 Correct 601 ms 33308 KB Output is correct
25 Correct 630 ms 33252 KB Output is correct
26 Correct 578 ms 33048 KB Output is correct
27 Correct 423 ms 21712 KB Output is correct
28 Correct 399 ms 21700 KB Output is correct
29 Correct 400 ms 21956 KB Output is correct
30 Correct 474 ms 21948 KB Output is correct
31 Correct 414 ms 21712 KB Output is correct
32 Partially correct 435 ms 21608 KB Output is partially correct
33 Correct 423 ms 21992 KB Output is correct
34 Correct 445 ms 21740 KB Output is correct
35 Correct 453 ms 21612 KB Output is correct
36 Correct 398 ms 21600 KB Output is correct
37 Partially correct 413 ms 22004 KB Output is partially correct
38 Correct 398 ms 22396 KB Output is correct
39 Correct 566 ms 30620 KB Output is correct
40 Correct 605 ms 30356 KB Output is correct
41 Correct 563 ms 30508 KB Output is correct
42 Correct 569 ms 30248 KB Output is correct