oj.uz

Submission #75064

# Submission time Handle Problem Language Result Execution time Memory
75064 2018-09-08T08:17:43 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 729 ms 33308 KB 
#include "highway.h"



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


mt19937 rng(409887653);
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 3 ms 376 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 416 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 376 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 36 ms 2640 KB Output is correct
3 Correct 384 ms 21220 KB Output is correct
4 Correct 515 ms 21220 KB Output is correct
5 Correct 413 ms 21208 KB Output is correct
6 Correct 480 ms 21220 KB Output is correct
7 Correct 359 ms 21220 KB Output is correct
8 Correct 371 ms 21224 KB Output is correct
9 Correct 408 ms 21296 KB Output is correct
10 Correct 370 ms 21220 KB Output is correct
11 Correct 364 ms 22452 KB Output is correct
12 Correct 424 ms 24180 KB Output is correct
13 Correct 396 ms 23860 KB Output is correct
14 Correct 395 ms 22448 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3440 KB Output is correct
2 Correct 50 ms 6556 KB Output is correct
3 Correct 66 ms 8840 KB Output is correct
4 Correct 234 ms 26532 KB Output is correct
5 Correct 210 ms 26540 KB Output is correct
6 Correct 345 ms 26292 KB Output is correct
7 Correct 218 ms 26628 KB Output is correct
8 Correct 226 ms 26296 KB Output is correct
9 Correct 351 ms 26552 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 540 KB Output is correct
2 Correct 30 ms 2620 KB Output is correct
3 Correct 244 ms 16512 KB Output is correct
4 Correct 374 ms 21240 KB Output is correct
5 Correct 385 ms 21228 KB Output is correct
6 Correct 324 ms 21224 KB Output is correct
7 Correct 378 ms 21220 KB Output is correct
8 Correct 347 ms 21184 KB Output is correct
9 Correct 373 ms 21220 KB Output is correct
10 Correct 397 ms 21228 KB Output is correct
11 Correct 380 ms 21988 KB Output is correct
12 Correct 389 ms 22796 KB Output is correct
13 Correct 393 ms 23456 KB Output is correct
14 Correct 461 ms 22324 KB Output is correct
15 Correct 366 ms 21208 KB Output is correct
16 Correct 349 ms 20876 KB Output is correct
17 Correct 490 ms 23004 KB Output is correct
18 Correct 489 ms 23040 KB Output is correct
19 Correct 384 ms 21284 KB Output is correct
20 Correct 380 ms 22984 KB Output is correct
21 Correct 380 ms 21388 KB Output is correct
22 Correct 345 ms 21388 KB Output is correct
23 Correct 331 ms 21540 KB Output is correct
24 Correct 336 ms 22140 KB Output is correct
25 Correct 440 ms 28264 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2972 KB Output is correct
2 Correct 35 ms 3232 KB Output is correct
3 Correct 429 ms 24536 KB Output is correct
4 Correct 625 ms 27140 KB Output is correct
5 Correct 699 ms 31772 KB Output is correct
6 Correct 729 ms 31724 KB Output is correct
7 Correct 614 ms 31568 KB Output is correct
8 Correct 517 ms 31744 KB Output is correct
9 Correct 519 ms 24292 KB Output is correct
10 Correct 569 ms 24772 KB Output is correct
11 Correct 622 ms 25332 KB Output is correct
12 Correct 583 ms 30712 KB Output is correct
13 Correct 567 ms 31220 KB Output is correct
14 Correct 581 ms 33092 KB Output is correct
15 Correct 715 ms 33112 KB Output is correct
16 Correct 576 ms 28312 KB Output is correct
17 Correct 474 ms 21460 KB Output is correct
18 Correct 452 ms 21716 KB Output is correct
19 Correct 386 ms 21708 KB Output is correct
20 Correct 430 ms 21792 KB Output is correct
21 Correct 539 ms 30348 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2972 KB Output is correct
2 Correct 64 ms 3236 KB Output is correct
3 Correct 414 ms 24888 KB Output is correct
4 Correct 470 ms 25900 KB Output is correct
5 Correct 476 ms 27156 KB Output is correct
6 Correct 642 ms 31708 KB Output is correct
7 Correct 446 ms 24812 KB Output is correct
8 Correct 448 ms 25912 KB Output is correct
9 Correct 451 ms 27156 KB Output is correct
10 Correct 581 ms 31724 KB Output is correct
11 Correct 564 ms 31716 KB Output is correct
12 Correct 604 ms 31724 KB Output is correct
13 Correct 507 ms 25316 KB Output is correct
14 Correct 621 ms 24788 KB Output is correct
15 Correct 504 ms 25224 KB Output is correct
16 Correct 560 ms 24752 KB Output is correct
17 Correct 622 ms 25320 KB Output is correct
18 Correct 575 ms 24720 KB Output is correct
19 Correct 550 ms 31436 KB Output is correct
20 Correct 540 ms 32304 KB Output is correct
21 Correct 574 ms 33212 KB Output is correct
22 Correct 620 ms 33228 KB Output is correct
23 Correct 534 ms 33104 KB Output is correct
24 Correct 573 ms 33308 KB Output is correct
25 Correct 564 ms 33260 KB Output is correct
26 Correct 607 ms 33080 KB Output is correct
27 Correct 356 ms 21720 KB Output is correct
28 Correct 384 ms 21652 KB Output is correct
29 Correct 394 ms 21856 KB Output is correct
30 Correct 398 ms 21924 KB Output is correct
31 Partially correct 371 ms 21644 KB Output is partially correct
32 Correct 369 ms 21588 KB Output is correct
33 Correct 395 ms 21968 KB Output is correct
34 Correct 385 ms 21720 KB Output is correct
35 Correct 371 ms 21596 KB Output is correct
36 Correct 381 ms 21584 KB Output is correct
37 Correct 384 ms 21976 KB Output is correct
38 Correct 403 ms 22308 KB Output is correct
39 Correct 536 ms 31520 KB Output is correct
40 Correct 547 ms 31212 KB Output is correct
41 Correct 547 ms 30984 KB Output is correct
42 Correct 527 ms 29948 KB Output is correct