oj.uz

Submission #75069

# Submission time Handle Problem Language Result Execution time Memory
75069 2018-09-08T08:27:41 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 696 ms 33368 KB 
#include "highway.h"



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


mt19937 rng(56246232);
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 296 KB Output is correct
2 Correct 3 ms 396 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 248 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 416 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 420 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 540 KB Output is correct
2 Correct 31 ms 2636 KB Output is correct
3 Correct 391 ms 21216 KB Output is correct
4 Correct 361 ms 21216 KB Output is correct
5 Correct 364 ms 21216 KB Output is correct
6 Correct 395 ms 21220 KB Output is correct
7 Correct 361 ms 21208 KB Output is correct
8 Correct 391 ms 21220 KB Output is correct
9 Correct 376 ms 21220 KB Output is correct
10 Correct 377 ms 21152 KB Output is correct
11 Correct 502 ms 23040 KB Output is correct
12 Correct 378 ms 23268 KB Output is correct
13 Correct 383 ms 22500 KB Output is correct
14 Correct 364 ms 22904 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3080 KB Output is correct
2 Correct 47 ms 5880 KB Output is correct
3 Correct 63 ms 8424 KB Output is correct
4 Correct 214 ms 28396 KB Output is correct
5 Correct 194 ms 28452 KB Output is correct
6 Correct 223 ms 28144 KB Output is correct
7 Correct 227 ms 28472 KB Output is correct
8 Correct 219 ms 28148 KB Output is correct
9 Correct 248 ms 28512 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 548 KB Output is correct
2 Correct 29 ms 2596 KB Output is correct
3 Correct 253 ms 16516 KB Output is correct
4 Correct 330 ms 21208 KB Output is correct
5 Correct 345 ms 21240 KB Output is correct
6 Correct 462 ms 21208 KB Output is correct
7 Correct 330 ms 21212 KB Output is correct
8 Correct 377 ms 21208 KB Output is correct
9 Correct 381 ms 21216 KB Output is correct
10 Correct 373 ms 21216 KB Output is correct
11 Correct 396 ms 22252 KB Output is correct
12 Correct 380 ms 23308 KB Output is correct
13 Correct 407 ms 22996 KB Output is correct
14 Correct 377 ms 22996 KB Output is correct
15 Correct 356 ms 21212 KB Output is correct
16 Correct 375 ms 21248 KB Output is correct
17 Correct 437 ms 23428 KB Output is correct
18 Correct 394 ms 23312 KB Output is correct
19 Correct 373 ms 21184 KB Output is correct
20 Correct 369 ms 23208 KB Output is correct
21 Correct 365 ms 21500 KB Output is correct
22 Correct 368 ms 21428 KB Output is correct
23 Correct 348 ms 21472 KB Output is correct
24 Correct 371 ms 22136 KB Output is correct
25 Correct 429 ms 26268 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3020 KB Output is correct
2 Correct 46 ms 3296 KB Output is correct
3 Correct 463 ms 24556 KB Output is correct
4 Correct 498 ms 27176 KB Output is correct
5 Correct 625 ms 31728 KB Output is correct
6 Correct 581 ms 31708 KB Output is correct
7 Correct 601 ms 31568 KB Output is correct
8 Correct 617 ms 31836 KB Output is correct
9 Correct 528 ms 24304 KB Output is correct
10 Correct 526 ms 24740 KB Output is correct
11 Correct 615 ms 25368 KB Output is correct
12 Correct 586 ms 30732 KB Output is correct
13 Correct 576 ms 31236 KB Output is correct
14 Correct 696 ms 33152 KB Output is correct
15 Correct 627 ms 33156 KB Output is correct
16 Correct 575 ms 28344 KB Output is correct
17 Correct 392 ms 21468 KB Output is correct
18 Correct 373 ms 21744 KB Output is correct
19 Correct 415 ms 21724 KB Output is correct
20 Correct 430 ms 21812 KB Output is correct
21 Correct 549 ms 30560 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3008 KB Output is correct
2 Correct 63 ms 3268 KB Output is correct
3 Correct 440 ms 24872 KB Output is correct
4 Correct 462 ms 25876 KB Output is correct
5 Correct 511 ms 27168 KB Output is correct
6 Correct 609 ms 31792 KB Output is correct
7 Correct 442 ms 24844 KB Output is correct
8 Correct 484 ms 25932 KB Output is correct
9 Correct 515 ms 27244 KB Output is correct
10 Correct 590 ms 31752 KB Output is correct
11 Correct 585 ms 31800 KB Output is correct
12 Correct 686 ms 31720 KB Output is correct
13 Correct 531 ms 25480 KB Output is correct
14 Correct 552 ms 24704 KB Output is correct
15 Correct 560 ms 25264 KB Output is correct
16 Correct 578 ms 24748 KB Output is correct
17 Correct 620 ms 25356 KB Output is correct
18 Correct 586 ms 24792 KB Output is correct
19 Correct 598 ms 31460 KB Output is correct
20 Correct 614 ms 32340 KB Output is correct
21 Correct 624 ms 33228 KB Output is correct
22 Correct 579 ms 33212 KB Output is correct
23 Correct 575 ms 33160 KB Output is correct
24 Correct 608 ms 33368 KB Output is correct
25 Correct 633 ms 33308 KB Output is correct
26 Correct 611 ms 33092 KB Output is correct
27 Correct 387 ms 21716 KB Output is correct
28 Correct 404 ms 21656 KB Output is correct
29 Partially correct 432 ms 21892 KB Output is partially correct
30 Partially correct 426 ms 22036 KB Output is partially correct
31 Correct 398 ms 21664 KB Output is correct
32 Correct 405 ms 21696 KB Output is correct
33 Correct 433 ms 22092 KB Output is correct
34 Correct 417 ms 21752 KB Output is correct
35 Correct 417 ms 21616 KB Output is correct
36 Correct 391 ms 21592 KB Output is correct
37 Correct 416 ms 22040 KB Output is correct
38 Correct 458 ms 22320 KB Output is correct
39 Correct 588 ms 29828 KB Output is correct
40 Correct 559 ms 30200 KB Output is correct
41 Correct 555 ms 31204 KB Output is correct
42 Correct 569 ms 30952 KB Output is correct