oj.uz

Submission #75063

# Submission time Handle Problem Language Result Execution time Memory
75063 2018-09-08T08:15:34 Z dacin21 Highway Tolls (IOI18_highway) C++14
90 / 100
 745 ms 33256 KB 
#include "highway.h"



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


mt19937 rng(521987423);
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 340 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 248 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 296 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 536 KB Output is correct
2 Correct 56 ms 2636 KB Output is correct
3 Correct 505 ms 21228 KB Output is correct
4 Correct 493 ms 21232 KB Output is correct
5 Correct 398 ms 21208 KB Output is correct
6 Correct 345 ms 21216 KB Output is correct
7 Correct 374 ms 21216 KB Output is correct
8 Correct 373 ms 21224 KB Output is correct
9 Correct 344 ms 21216 KB Output is correct
10 Correct 355 ms 21208 KB Output is correct
11 Correct 373 ms 22388 KB Output is correct
12 Correct 351 ms 23040 KB Output is correct
13 Correct 435 ms 23240 KB Output is correct
14 Correct 356 ms 22004 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3076 KB Output is correct
2 Correct 84 ms 6116 KB Output is correct
3 Correct 58 ms 8980 KB Output is correct
4 Correct 342 ms 26208 KB Output is correct
5 Correct 215 ms 26212 KB Output is correct
6 Correct 221 ms 25956 KB Output is correct
7 Correct 272 ms 26316 KB Output is correct
8 Correct 214 ms 25948 KB Output is correct
9 Correct 228 ms 26232 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 28 ms 2636 KB Output is correct
3 Correct 248 ms 16504 KB Output is correct
4 Correct 361 ms 21212 KB Output is correct
5 Correct 328 ms 21220 KB Output is correct
6 Correct 452 ms 21224 KB Output is correct
7 Correct 312 ms 21220 KB Output is correct
8 Correct 405 ms 21200 KB Output is correct
9 Correct 397 ms 21204 KB Output is correct
10 Correct 392 ms 21228 KB Output is correct
11 Correct 423 ms 21924 KB Output is correct
12 Correct 379 ms 22576 KB Output is correct
13 Correct 385 ms 22760 KB Output is correct
14 Correct 383 ms 23256 KB Output is correct
15 Correct 375 ms 21220 KB Output is correct
16 Correct 326 ms 20868 KB Output is correct
17 Correct 373 ms 22524 KB Output is correct
18 Correct 491 ms 22536 KB Output is correct
19 Correct 309 ms 21248 KB Output is correct
20 Correct 355 ms 23420 KB Output is correct
21 Correct 462 ms 21384 KB Output is correct
22 Correct 469 ms 21372 KB Output is correct
23 Correct 336 ms 21460 KB Output is correct
24 Correct 313 ms 21868 KB Output is correct
25 Correct 416 ms 24968 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2984 KB Output is correct
2 Correct 40 ms 3236 KB Output is correct
3 Correct 400 ms 24556 KB Output is correct
4 Correct 484 ms 27124 KB Output is correct
5 Correct 585 ms 31708 KB Output is correct
6 Correct 569 ms 31712 KB Output is correct
7 Correct 552 ms 31560 KB Output is correct
8 Correct 543 ms 31708 KB Output is correct
9 Correct 489 ms 24300 KB Output is correct
10 Correct 538 ms 24748 KB Output is correct
11 Correct 526 ms 25340 KB Output is correct
12 Correct 560 ms 30696 KB Output is correct
13 Correct 567 ms 31248 KB Output is correct
14 Correct 705 ms 33076 KB Output is correct
15 Correct 625 ms 33108 KB Output is correct
16 Correct 533 ms 28328 KB Output is correct
17 Correct 367 ms 21456 KB Output is correct
18 Correct 394 ms 21716 KB Output is correct
19 Correct 396 ms 21720 KB Output is correct
20 Correct 373 ms 21784 KB Output is correct
21 Correct 548 ms 29940 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2976 KB Output is correct
2 Correct 69 ms 3256 KB Output is correct
3 Correct 456 ms 24832 KB Output is correct
4 Correct 486 ms 25888 KB Output is correct
5 Correct 473 ms 27120 KB Output is correct
6 Correct 745 ms 31720 KB Output is correct
7 Correct 417 ms 24852 KB Output is correct
8 Correct 465 ms 25916 KB Output is correct
9 Correct 631 ms 27148 KB Output is correct
10 Correct 582 ms 31716 KB Output is correct
11 Correct 588 ms 31756 KB Output is correct
12 Correct 616 ms 31688 KB Output is correct
13 Correct 514 ms 25312 KB Output is correct
14 Correct 448 ms 24688 KB Output is correct
15 Correct 549 ms 25248 KB Output is correct
16 Correct 526 ms 24704 KB Output is correct
17 Correct 539 ms 25348 KB Output is correct
18 Correct 505 ms 24696 KB Output is correct
19 Correct 553 ms 31448 KB Output is correct
20 Correct 582 ms 32292 KB Output is correct
21 Correct 610 ms 33220 KB Output is correct
22 Correct 582 ms 33236 KB Output is correct
23 Correct 632 ms 33080 KB Output is correct
24 Correct 628 ms 33248 KB Output is correct
25 Correct 730 ms 33256 KB Output is correct
26 Correct 599 ms 33084 KB Output is correct
27 Correct 356 ms 21732 KB Output is correct
28 Correct 391 ms 21636 KB Output is correct
29 Correct 415 ms 21864 KB Output is correct
30 Correct 506 ms 21944 KB Output is correct
31 Correct 388 ms 21640 KB Output is correct
32 Correct 390 ms 21584 KB Output is correct
33 Partially correct 377 ms 21968 KB Output is partially correct
34 Correct 443 ms 21728 KB Output is correct
35 Correct 359 ms 21592 KB Output is correct
36 Correct 508 ms 21580 KB Output is correct
37 Correct 410 ms 21972 KB Output is correct
38 Correct 370 ms 22308 KB Output is correct
39 Correct 524 ms 30848 KB Output is correct
40 Correct 681 ms 31268 KB Output is correct
41 Correct 518 ms 30312 KB Output is correct
42 Correct 545 ms 30400 KB Output is correct