oj.uz

Submission #75059

# Submission time Handle Problem Language Result Execution time Memory
75059 2018-09-08T08:07:12 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 728 ms 33328 KB 
// 51 queries
#include "highway.h"



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


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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 544 KB Output is correct
2 Correct 30 ms 2620 KB Output is correct
3 Correct 390 ms 21216 KB Output is correct
4 Correct 359 ms 21216 KB Output is correct
5 Correct 384 ms 21212 KB Output is correct
6 Correct 482 ms 21228 KB Output is correct
7 Correct 357 ms 21232 KB Output is correct
8 Correct 361 ms 21224 KB Output is correct
9 Correct 379 ms 21216 KB Output is correct
10 Correct 515 ms 21224 KB Output is correct
11 Correct 493 ms 23220 KB Output is correct
12 Correct 506 ms 23900 KB Output is correct
13 Correct 346 ms 22576 KB Output is correct
14 Correct 407 ms 22500 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3200 KB Output is correct
2 Correct 40 ms 6412 KB Output is correct
3 Correct 58 ms 9120 KB Output is correct
4 Correct 218 ms 28336 KB Output is correct
5 Correct 203 ms 28280 KB Output is correct
6 Correct 240 ms 28004 KB Output is correct
7 Correct 345 ms 28376 KB Output is correct
8 Correct 223 ms 28004 KB Output is correct
9 Correct 234 ms 28320 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 552 KB Output is correct
2 Correct 32 ms 2632 KB Output is correct
3 Correct 262 ms 16504 KB Output is correct
4 Correct 360 ms 21224 KB Output is correct
5 Correct 365 ms 21224 KB Output is correct
6 Correct 341 ms 21328 KB Output is correct
7 Correct 330 ms 21204 KB Output is correct
8 Correct 331 ms 21196 KB Output is correct
9 Correct 346 ms 21224 KB Output is correct
10 Correct 362 ms 21276 KB Output is correct
11 Correct 411 ms 21856 KB Output is correct
12 Correct 372 ms 22500 KB Output is correct
13 Correct 391 ms 23032 KB Output is correct
14 Correct 493 ms 22404 KB Output is correct
15 Correct 377 ms 21224 KB Output is correct
16 Correct 339 ms 21216 KB Output is correct
17 Correct 459 ms 22644 KB Output is correct
18 Correct 441 ms 22156 KB Output is correct
19 Correct 499 ms 21216 KB Output is correct
20 Correct 512 ms 24264 KB Output is correct
21 Correct 382 ms 21384 KB Output is correct
22 Correct 337 ms 21412 KB Output is correct
23 Correct 329 ms 21464 KB Output is correct
24 Correct 347 ms 22132 KB Output is correct
25 Correct 420 ms 28268 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2980 KB Output is correct
2 Correct 34 ms 3244 KB Output is correct
3 Correct 434 ms 24544 KB Output is correct
4 Correct 604 ms 27152 KB Output is correct
5 Correct 560 ms 31704 KB Output is correct
6 Correct 528 ms 31736 KB Output is correct
7 Correct 555 ms 31592 KB Output is correct
8 Correct 573 ms 31716 KB Output is correct
9 Correct 482 ms 24212 KB Output is correct
10 Correct 515 ms 24780 KB Output is correct
11 Correct 703 ms 25324 KB Output is correct
12 Correct 553 ms 30716 KB Output is correct
13 Correct 556 ms 31224 KB Output is correct
14 Correct 580 ms 33108 KB Output is correct
15 Correct 552 ms 33108 KB Output is correct
16 Correct 669 ms 28312 KB Output is correct
17 Correct 450 ms 21476 KB Output is correct
18 Correct 481 ms 21712 KB Output is correct
19 Correct 385 ms 21708 KB Output is correct
20 Correct 400 ms 21784 KB Output is correct
21 Correct 549 ms 30064 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2992 KB Output is correct
2 Correct 32 ms 3224 KB Output is correct
3 Correct 387 ms 24836 KB Output is correct
4 Correct 454 ms 25996 KB Output is correct
5 Correct 419 ms 27112 KB Output is correct
6 Correct 565 ms 31696 KB Output is correct
7 Correct 433 ms 24840 KB Output is correct
8 Correct 410 ms 25956 KB Output is correct
9 Correct 485 ms 27156 KB Output is correct
10 Correct 557 ms 31732 KB Output is correct
11 Correct 563 ms 31760 KB Output is correct
12 Correct 555 ms 31708 KB Output is correct
13 Correct 521 ms 25316 KB Output is correct
14 Correct 514 ms 24688 KB Output is correct
15 Correct 551 ms 25232 KB Output is correct
16 Correct 668 ms 24704 KB Output is correct
17 Correct 548 ms 25312 KB Output is correct
18 Correct 685 ms 24692 KB Output is correct
19 Correct 529 ms 31432 KB Output is correct
20 Correct 508 ms 32332 KB Output is correct
21 Correct 577 ms 33284 KB Output is correct
22 Correct 728 ms 33232 KB Output is correct
23 Correct 591 ms 33108 KB Output is correct
24 Correct 722 ms 33328 KB Output is correct
25 Correct 666 ms 33220 KB Output is correct
26 Correct 599 ms 33116 KB Output is correct
27 Partially correct 501 ms 21700 KB Output is partially correct
28 Correct 381 ms 21648 KB Output is correct
29 Correct 399 ms 21856 KB Output is correct
30 Correct 389 ms 21940 KB Output is correct
31 Correct 358 ms 21784 KB Output is correct
32 Correct 380 ms 21592 KB Output is correct
33 Correct 392 ms 21956 KB Output is correct
34 Correct 379 ms 21724 KB Output is correct
35 Correct 369 ms 21600 KB Output is correct
36 Partially correct 382 ms 21568 KB Output is partially correct
37 Correct 393 ms 21996 KB Output is correct
38 Correct 438 ms 22288 KB Output is correct
39 Correct 501 ms 30888 KB Output is correct
40 Correct 551 ms 30732 KB Output is correct
41 Correct 676 ms 30404 KB Output is correct
42 Correct 530 ms 30884 KB Output is correct