oj.uz

Submission #75068

# Submission time Handle Problem Language Result Execution time Memory
75068 2018-09-08T08:25:25 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 707 ms 33304 KB 
#include "highway.h"



#include <bits/stdc++.h>
using namespace std;
using ll = long long;


mt19937 rng(56246231);
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:18: 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 3 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 296 KB Output is correct
11 Correct 2 ms 416 KB Output is correct
12 Correct 2 ms 332 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 30 ms 2660 KB Output is correct
3 Correct 514 ms 21228 KB Output is correct
4 Correct 457 ms 21208 KB Output is correct
5 Correct 400 ms 21204 KB Output is correct
6 Correct 348 ms 21212 KB Output is correct
7 Correct 367 ms 21216 KB Output is correct
8 Correct 398 ms 21224 KB Output is correct
9 Correct 460 ms 21216 KB Output is correct
10 Correct 374 ms 21224 KB Output is correct
11 Correct 397 ms 22784 KB Output is correct
12 Correct 539 ms 23540 KB Output is correct
13 Correct 413 ms 22784 KB Output is correct
14 Correct 369 ms 22504 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3144 KB Output is correct
2 Correct 38 ms 5856 KB Output is correct
3 Correct 71 ms 8892 KB Output is correct
4 Correct 226 ms 27088 KB Output is correct
5 Correct 210 ms 27100 KB Output is correct
6 Correct 198 ms 26836 KB Output is correct
7 Correct 224 ms 27084 KB Output is correct
8 Correct 217 ms 26832 KB Output is correct
9 Correct 237 ms 27168 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 33 ms 2628 KB Output is correct
3 Correct 352 ms 16508 KB Output is correct
4 Correct 337 ms 21224 KB Output is correct
5 Correct 331 ms 21212 KB Output is correct
6 Correct 359 ms 21212 KB Output is correct
7 Correct 475 ms 21184 KB Output is correct
8 Correct 364 ms 21196 KB Output is correct
9 Correct 362 ms 21216 KB Output is correct
10 Correct 469 ms 21216 KB Output is correct
11 Correct 514 ms 22256 KB Output is correct
12 Correct 382 ms 22412 KB Output is correct
13 Correct 388 ms 22176 KB Output is correct
14 Correct 505 ms 23392 KB Output is correct
15 Correct 335 ms 21216 KB Output is correct
16 Correct 352 ms 21216 KB Output is correct
17 Correct 498 ms 23184 KB Output is correct
18 Correct 389 ms 23412 KB Output is correct
19 Correct 352 ms 21228 KB Output is correct
20 Correct 362 ms 24372 KB Output is correct
21 Correct 467 ms 21392 KB Output is correct
22 Correct 334 ms 21380 KB Output is correct
23 Correct 337 ms 21460 KB Output is correct
24 Correct 459 ms 22124 KB Output is correct
25 Correct 547 ms 28276 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2992 KB Output is correct
2 Correct 34 ms 3244 KB Output is correct
3 Correct 413 ms 24552 KB Output is correct
4 Correct 482 ms 27144 KB Output is correct
5 Correct 570 ms 31796 KB Output is correct
6 Correct 553 ms 31708 KB Output is correct
7 Correct 563 ms 31584 KB Output is correct
8 Correct 536 ms 31744 KB Output is correct
9 Correct 499 ms 24220 KB Output is correct
10 Correct 540 ms 24752 KB Output is correct
11 Correct 533 ms 25340 KB Output is correct
12 Correct 589 ms 30724 KB Output is correct
13 Correct 552 ms 31224 KB Output is correct
14 Correct 519 ms 33096 KB Output is correct
15 Correct 579 ms 33056 KB Output is correct
16 Correct 548 ms 28312 KB Output is correct
17 Correct 366 ms 21492 KB Output is correct
18 Correct 399 ms 21744 KB Output is correct
19 Correct 396 ms 21720 KB Output is correct
20 Correct 433 ms 21796 KB Output is correct
21 Correct 570 ms 30452 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3016 KB Output is correct
2 Correct 43 ms 3256 KB Output is correct
3 Correct 452 ms 24852 KB Output is correct
4 Correct 474 ms 25912 KB Output is correct
5 Correct 500 ms 27144 KB Output is correct
6 Correct 614 ms 31736 KB Output is correct
7 Correct 452 ms 24864 KB Output is correct
8 Correct 459 ms 25884 KB Output is correct
9 Correct 525 ms 27132 KB Output is correct
10 Correct 604 ms 31828 KB Output is correct
11 Correct 598 ms 31740 KB Output is correct
12 Correct 597 ms 31756 KB Output is correct
13 Correct 545 ms 25352 KB Output is correct
14 Correct 603 ms 24768 KB Output is correct
15 Correct 620 ms 25264 KB Output is correct
16 Correct 576 ms 24700 KB Output is correct
17 Correct 615 ms 25348 KB Output is correct
18 Correct 575 ms 24816 KB Output is correct
19 Correct 583 ms 31436 KB Output is correct
20 Correct 601 ms 32376 KB Output is correct
21 Correct 639 ms 33304 KB Output is correct
22 Correct 596 ms 33264 KB Output is correct
23 Correct 549 ms 33144 KB Output is correct
24 Correct 612 ms 33272 KB Output is correct
25 Correct 665 ms 33280 KB Output is correct
26 Correct 707 ms 33192 KB Output is correct
27 Correct 427 ms 21764 KB Output is correct
28 Correct 411 ms 21732 KB Output is correct
29 Correct 467 ms 21948 KB Output is correct
30 Correct 418 ms 22008 KB Output is correct
31 Correct 411 ms 21660 KB Output is correct
32 Partially correct 430 ms 21596 KB Output is partially correct
33 Correct 422 ms 21960 KB Output is correct
34 Correct 397 ms 21836 KB Output is correct
35 Correct 423 ms 21616 KB Output is correct
36 Correct 395 ms 21592 KB Output is correct
37 Correct 428 ms 21996 KB Output is correct
38 Correct 459 ms 22404 KB Output is correct
39 Correct 540 ms 30604 KB Output is correct
40 Correct 564 ms 30840 KB Output is correct
41 Correct 534 ms 30256 KB Output is correct
42 Correct 591 ms 31060 KB Output is correct