oj.uz

Submission #75073

# Submission time Handle Problem Language Result Execution time Memory
75073 2018-09-08T08:38:57 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 726 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()^3)%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 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 332 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 292 KB Output is correct
11 Correct 2 ms 376 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 464 KB Output is correct
2 Correct 44 ms 2652 KB Output is correct
3 Correct 394 ms 21224 KB Output is correct
4 Correct 398 ms 21228 KB Output is correct
5 Correct 372 ms 21236 KB Output is correct
6 Correct 382 ms 21236 KB Output is correct
7 Correct 388 ms 21340 KB Output is correct
8 Correct 381 ms 21228 KB Output is correct
9 Correct 410 ms 21240 KB Output is correct
10 Correct 407 ms 21228 KB Output is correct
11 Correct 402 ms 23088 KB Output is correct
12 Correct 420 ms 23588 KB Output is correct
13 Correct 399 ms 22504 KB Output is correct
14 Correct 409 ms 22344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3324 KB Output is correct
2 Correct 69 ms 6468 KB Output is correct
3 Correct 85 ms 9368 KB Output is correct
4 Correct 241 ms 26552 KB Output is correct
5 Correct 291 ms 27148 KB Output is correct
6 Correct 260 ms 28380 KB Output is correct
7 Correct 289 ms 28324 KB Output is correct
8 Correct 257 ms 28088 KB Output is correct
9 Correct 250 ms 28628 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 39 ms 2628 KB Output is correct
3 Correct 271 ms 16544 KB Output is correct
4 Correct 385 ms 21224 KB Output is correct
5 Correct 368 ms 21228 KB Output is correct
6 Correct 357 ms 21224 KB Output is correct
7 Correct 354 ms 21304 KB Output is correct
8 Correct 370 ms 21188 KB Output is correct
9 Correct 373 ms 21220 KB Output is correct
10 Correct 412 ms 21232 KB Output is correct
11 Correct 411 ms 22244 KB Output is correct
12 Correct 390 ms 22412 KB Output is correct
13 Correct 395 ms 22240 KB Output is correct
14 Correct 386 ms 22332 KB Output is correct
15 Correct 365 ms 21232 KB Output is correct
16 Correct 374 ms 21212 KB Output is correct
17 Correct 411 ms 23176 KB Output is correct
18 Correct 396 ms 23128 KB Output is correct
19 Correct 375 ms 21232 KB Output is correct
20 Correct 389 ms 24400 KB Output is correct
21 Correct 350 ms 21508 KB Output is correct
22 Correct 367 ms 21396 KB Output is correct
23 Correct 375 ms 21512 KB Output is correct
24 Correct 377 ms 22188 KB Output is correct
25 Correct 465 ms 28268 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2984 KB Output is correct
2 Correct 43 ms 3380 KB Output is correct
3 Correct 448 ms 24552 KB Output is correct
4 Correct 537 ms 27156 KB Output is correct
5 Correct 617 ms 31832 KB Output is correct
6 Correct 610 ms 31732 KB Output is correct
7 Correct 622 ms 31576 KB Output is correct
8 Correct 603 ms 31676 KB Output is correct
9 Correct 535 ms 24296 KB Output is correct
10 Correct 726 ms 24856 KB Output is correct
11 Correct 626 ms 25360 KB Output is correct
12 Correct 594 ms 30716 KB Output is correct
13 Correct 554 ms 31264 KB Output is correct
14 Correct 625 ms 33116 KB Output is correct
15 Correct 632 ms 33112 KB Output is correct
16 Correct 598 ms 28384 KB Output is correct
17 Correct 418 ms 21468 KB Output is correct
18 Correct 449 ms 21732 KB Output is correct
19 Correct 429 ms 21716 KB Output is correct
20 Correct 432 ms 21800 KB Output is correct
21 Correct 572 ms 30392 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3004 KB Output is correct
2 Correct 43 ms 3240 KB Output is correct
3 Correct 435 ms 24868 KB Output is correct
4 Correct 465 ms 25888 KB Output is correct
5 Correct 515 ms 27136 KB Output is correct
6 Correct 598 ms 31732 KB Output is correct
7 Correct 450 ms 24848 KB Output is correct
8 Correct 483 ms 25900 KB Output is correct
9 Correct 487 ms 27184 KB Output is correct
10 Correct 623 ms 31776 KB Output is correct
11 Correct 629 ms 31784 KB Output is correct
12 Correct 605 ms 31824 KB Output is correct
13 Correct 539 ms 25452 KB Output is correct
14 Correct 517 ms 24696 KB Output is correct
15 Correct 637 ms 25248 KB Output is correct
16 Correct 574 ms 24712 KB Output is correct
17 Correct 647 ms 25428 KB Output is correct
18 Correct 563 ms 24800 KB Output is correct
19 Correct 613 ms 31436 KB Output is correct
20 Correct 624 ms 32408 KB Output is correct
21 Correct 629 ms 33316 KB Output is correct
22 Correct 601 ms 33248 KB Output is correct
23 Correct 606 ms 33096 KB Output is correct
24 Correct 598 ms 33296 KB Output is correct
25 Correct 622 ms 33296 KB Output is correct
26 Correct 641 ms 33100 KB Output is correct
27 Correct 387 ms 21708 KB Output is correct
28 Correct 395 ms 21652 KB Output is correct
29 Correct 412 ms 21876 KB Output is correct
30 Correct 409 ms 21940 KB Output is correct
31 Partially correct 403 ms 21648 KB Output is partially correct
32 Correct 397 ms 21604 KB Output is correct
33 Correct 406 ms 21992 KB Output is correct
34 Correct 407 ms 21748 KB Output is correct
35 Correct 431 ms 21588 KB Output is correct
36 Correct 433 ms 21672 KB Output is correct
37 Correct 420 ms 22052 KB Output is correct
38 Correct 428 ms 22324 KB Output is correct
39 Correct 558 ms 31548 KB Output is correct
40 Correct 541 ms 30220 KB Output is correct
41 Correct 560 ms 30536 KB Output is correct
42 Correct 575 ms 30156 KB Output is correct