oj.uz

Submission #349133

# Submission time Handle Problem Language Result Execution time Memory
349133 2021-01-16T18:42:18 Z milleniumEeee Highway Tolls (IOI18_highway) C++17
100 / 100
 715 ms 37632 KB 
#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define pb push_back
#define ll long long
using namespace std;
 
const int MAXN = 130005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
int n, m;
vector <pair<int, int>> G[MAXN]; // обычный граф
vector <pair<int, int>> tree[MAXN]; // дерево
int d[MAXN];
int tin[MAXN];
int tout[MAXN];
int tiktak = 0;
int edge[MAXN][2];
bool used[MAXN];
int ROOT, SUB_S;
vector <int> BFS_EDGES;
vector <int> bfs_edges[3]; // already sorted by id
map <pii, int> id;

ll costa, costb;
ll diametr;
ll min_path, max_path;

ll get_min_path() {
    vector <int> w(m);
    for (int i = 0; i < m; i++) {
        w[i] = 0;
    }
    ll cur_cost = ask(w);
    return cur_cost;
}
 
int find_root() {
    vector <int> w(m);
    for (int i = 0; i < m; i++) {
        w[i] = 0;
    }
    w[0] = 1;
    ll cur_cost;
    int l = -1, r = m - 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 0;
        }
        for (int i = 0; i <= mid; i++) {
            w[i] = 1;
        }
        cur_cost = ask(w);
        if (cur_cost == min_path) {
            l = mid;
        } else {
            r = mid;
        }
    }
    ROOT = edge[r][0];
    SUB_S = edge[r][1];
    return edge[r][0];
}

void create_tree(int root) {
    BFS_EDGES.clear();
    memset(used, 0, sizeof(used));
    for (int i = 0; i < MAXN; i++) {
        tree[i].clear();
    }
    // найти ребро на пути S -> T
    queue <int> q;
    vector <int> dist(MAXN, -1);
    dist[root] = 0;
    q.push(root);
    
    assert(id.count(mk(root, SUB_S)));
    
    for (int i = 1; i < szof(G[root]); i++) {
        if (G[root][i].fr == SUB_S) {
            swap(G[root][0], G[root][i]);
            break;
        }
    }
    
    // почему ? надо разобраться
    //int sub_id = id[mk(root, SUB_S)];
    //used[SUB_S] = true;
    //BFS_EDGES.pb(sub_id);
    //tree[root].pb({SUB_S, sub_id});
    //tree[sub_id].pb({SUB_S, root});
    //dist[SUB_S] = 1;
    //q.push(SUB_S);
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (pii to : G[v]) {
            if (dist[to.fr] == -1) {
                used[to.sc] = true;
                BFS_EDGES.pb(to.sc);
                tree[v].pb({to.fr, to.sc});
                tree[to.fr].pb({v, to.sc});
                dist[to.fr] = dist[v] + 1;
                q.push(to.fr);
            }
        }
    }
}
void calc(int v, int par, int len) {
    tin[v] = ++tiktak;
    d[v] = len;
    for (pii to : tree[v]) {
        if (to.fr != par) {
            calc(to.fr, v, len + 1);            
        }
    }
    tout[v] = tiktak;
}
bool father(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}
vector <int> subtree[3];
void dfs(int v, int par) {
    if (father(SUB_S, v)) {
        subtree[1].pb(v);
    } else {
        subtree[2].pb(v);
    }
    for (pii to : tree[v]) {
        if (to.fr != par) {
            dfs(to.fr, v);
        }
    }
}

int find_ans(int cur_root, vector <int> cur_bfs_edges) {
    if (cur_bfs_edges.empty()) {
        return cur_root;
    }
    int l = -1, r = szof(cur_bfs_edges);
    vector <int> w(m);
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 1;
        }
        for (int el : BFS_EDGES) {
            w[el] = 0;
        }
        for (int i = mid; i < szof(cur_bfs_edges); i++) {
            w[cur_bfs_edges[i]] = 1;
        }
        ll cur_cost = ask(w);
        if (cur_cost == min_path) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if (l == -1) {
        return cur_root;
    }
    int x = edge[cur_bfs_edges[l]][0];
    int y = edge[cur_bfs_edges[l]][1];
    return (d[x] > d[y] ? x : y);
}

void find_pair(int N, vector<int> U, vector<int> V, int AA, int BB) {
    m = szof(U);
    n = N;
    costa = AA;
    costb = BB;
    min_path = get_min_path(); // 1 q
    diametr = min_path / costa;
    max_path = diametr * costb;
    for (int i = 0; i < m; i++) {
        int x, y;
        x = U[i];
        y = V[i];
        id[{x, y}] = i;
        id[{y, x}] = i;
        edge[i][0] = x;
        edge[i][1] = y;
        G[x].pb({y, i});
        G[y].pb({x, i});
    }
    int s, t;
    int root = find_root(); // log(n)
    create_tree(root);
    calc(root, -1, 0);
    dfs(root, -1);
    sort(all(subtree[1]));
    sort(all(subtree[2]));
    auto exist = [&](vector <int> &vec, int x) {
        bool ok = binary_search(all(vec), x);
        return ok;
    };
    for (int el : BFS_EDGES) {
        int x = edge[el][0];
        int y = edge[el][1];
        if ((x == ROOT && y == SUB_S) || (x == SUB_S && y == ROOT)) {
            continue;
        }
        if (exist(subtree[1], x)) {
            bfs_edges[1].pb({id[{x, y}]});
        } else {
            bfs_edges[2].pb({id[{x, y}]});
        }
    }
    s = find_ans(SUB_S, bfs_edges[1]); // log(n) - 1
    t = find_ans(ROOT, bfs_edges[2]); // log(n) - 1
    answer(s, t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7020 KB Output is correct
2 Correct 5 ms 7020 KB Output is correct
3 Correct 5 ms 7020 KB Output is correct
4 Correct 5 ms 7128 KB Output is correct
5 Correct 5 ms 7020 KB Output is correct
6 Correct 5 ms 7020 KB Output is correct
7 Correct 5 ms 7020 KB Output is correct
8 Correct 5 ms 7168 KB Output is correct
9 Correct 5 ms 7020 KB Output is correct
10 Correct 5 ms 7020 KB Output is correct
11 Correct 5 ms 7128 KB Output is correct
12 Correct 5 ms 7020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7296 KB Output is correct
2 Correct 33 ms 9324 KB Output is correct
3 Correct 407 ms 29772 KB Output is correct
4 Correct 481 ms 29692 KB Output is correct
5 Correct 435 ms 29736 KB Output is correct
6 Correct 431 ms 29704 KB Output is correct
7 Correct 466 ms 29588 KB Output is correct
8 Correct 467 ms 29600 KB Output is correct
9 Correct 375 ms 29628 KB Output is correct
10 Correct 446 ms 29664 KB Output is correct
11 Correct 450 ms 29704 KB Output is correct
12 Correct 464 ms 30828 KB Output is correct
13 Correct 444 ms 29964 KB Output is correct
14 Correct 472 ms 29988 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9584 KB Output is correct
2 Correct 49 ms 12528 KB Output is correct
3 Correct 70 ms 15776 KB Output is correct
4 Correct 229 ms 31992 KB Output is correct
5 Correct 253 ms 32272 KB Output is correct
6 Correct 245 ms 33212 KB Output is correct
7 Correct 216 ms 34040 KB Output is correct
8 Correct 233 ms 32684 KB Output is correct
9 Correct 208 ms 33044 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7276 KB Output is correct
2 Correct 33 ms 9324 KB Output is correct
3 Correct 319 ms 24628 KB Output is correct
4 Correct 405 ms 29720 KB Output is correct
5 Correct 396 ms 29780 KB Output is correct
6 Correct 441 ms 29860 KB Output is correct
7 Correct 428 ms 29688 KB Output is correct
8 Correct 418 ms 29696 KB Output is correct
9 Correct 422 ms 29752 KB Output is correct
10 Correct 469 ms 29612 KB Output is correct
11 Correct 425 ms 29656 KB Output is correct
12 Correct 473 ms 30484 KB Output is correct
13 Correct 435 ms 30316 KB Output is correct
14 Correct 426 ms 30252 KB Output is correct
15 Correct 399 ms 29588 KB Output is correct
16 Correct 435 ms 29760 KB Output is correct
17 Correct 433 ms 29876 KB Output is correct
18 Correct 429 ms 30124 KB Output is correct
19 Correct 391 ms 29752 KB Output is correct
20 Correct 428 ms 30612 KB Output is correct
21 Correct 363 ms 30536 KB Output is correct
22 Correct 331 ms 30548 KB Output is correct
23 Correct 378 ms 30108 KB Output is correct
24 Correct 409 ms 30360 KB Output is correct
25 Correct 422 ms 33564 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9452 KB Output is correct
2 Correct 40 ms 9708 KB Output is correct
3 Correct 530 ms 31488 KB Output is correct
4 Correct 567 ms 33244 KB Output is correct
5 Correct 694 ms 36672 KB Output is correct
6 Correct 640 ms 36428 KB Output is correct
7 Correct 689 ms 36668 KB Output is correct
8 Correct 638 ms 36324 KB Output is correct
9 Correct 459 ms 31512 KB Output is correct
10 Correct 461 ms 32448 KB Output is correct
11 Correct 469 ms 33120 KB Output is correct
12 Correct 634 ms 35036 KB Output is correct
13 Correct 643 ms 35724 KB Output is correct
14 Correct 696 ms 36304 KB Output is correct
15 Correct 696 ms 36312 KB Output is correct
16 Correct 519 ms 32872 KB Output is correct
17 Correct 442 ms 30604 KB Output is correct
18 Correct 419 ms 30872 KB Output is correct
19 Correct 382 ms 30728 KB Output is correct
20 Correct 399 ms 30864 KB Output is correct
21 Correct 623 ms 36956 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9452 KB Output is correct
2 Correct 41 ms 9708 KB Output is correct
3 Correct 492 ms 31460 KB Output is correct
4 Correct 506 ms 32192 KB Output is correct
5 Correct 526 ms 33320 KB Output is correct
6 Correct 620 ms 36468 KB Output is correct
7 Correct 447 ms 31676 KB Output is correct
8 Correct 507 ms 32236 KB Output is correct
9 Correct 518 ms 32960 KB Output is correct
10 Correct 605 ms 36488 KB Output is correct
11 Correct 630 ms 36432 KB Output is correct
12 Correct 678 ms 36416 KB Output is correct
13 Correct 536 ms 33336 KB Output is correct
14 Correct 524 ms 32420 KB Output is correct
15 Correct 527 ms 33092 KB Output is correct
16 Correct 480 ms 32576 KB Output is correct
17 Correct 509 ms 33052 KB Output is correct
18 Correct 469 ms 32472 KB Output is correct
19 Correct 653 ms 35060 KB Output is correct
20 Correct 656 ms 35540 KB Output is correct
21 Correct 715 ms 36220 KB Output is correct
22 Correct 637 ms 36368 KB Output is correct
23 Correct 649 ms 36368 KB Output is correct
24 Correct 645 ms 36176 KB Output is correct
25 Correct 629 ms 36440 KB Output is correct
26 Correct 645 ms 36304 KB Output is correct
27 Correct 436 ms 30676 KB Output is correct
28 Correct 386 ms 30560 KB Output is correct
29 Correct 436 ms 31124 KB Output is correct
30 Correct 394 ms 30976 KB Output is correct
31 Correct 385 ms 30760 KB Output is correct
32 Correct 382 ms 30488 KB Output is correct
33 Correct 399 ms 30992 KB Output is correct
34 Correct 385 ms 30668 KB Output is correct
35 Correct 392 ms 30544 KB Output is correct
36 Correct 394 ms 30660 KB Output is correct
37 Correct 435 ms 31140 KB Output is correct
38 Correct 443 ms 31292 KB Output is correct
39 Correct 696 ms 37184 KB Output is correct
40 Correct 692 ms 37632 KB Output is correct
41 Correct 678 ms 36680 KB Output is correct
42 Correct 616 ms 36656 KB Output is correct