oj.uz

Submission #1057650

# Submission time Handle Problem Language Result Execution time Memory
1057650 2024-08-14T02:30:48 Z efishel Highway Tolls (IOI18_highway) C++17
90 / 100
 130 ms 26168 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1.3E5+16;
vii adj[MAXN];
vii adjT[MAXN];
bool vis[MAXN];
ll toPar[MAXN];
ll dep[MAXN];

vll ord;
void dfs (ll u, ll l, ll r) {
    vis[u] = true;
    for (auto [v, id] : adjT[u]) {
        if (vis[v]) continue;
        dep[v] = dep[u]+1;
        dfs(v, l, r);
        toPar[v] = id;
    }
    if (l <= dep[u] && dep[u] <= r) ord.push_back(u);
}

void find_pair (int n, vi us, vi vs, int a, int b) {
    ll m = us.size();
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back({ vs[i], i });
        adj[vs[i]].push_back({ us[i], i });
    }
    ll raw = ask(vi(m, 0));
    ll dis = raw/a;
    vi askMask(m, -15);
    ll src1 = -15, src2 = -15;
    {ll l = -1, r = m-1;
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(m, 0);
        for (ll i = 0; i <= mid; i++) vask[i] = 1;
        if (ask(vask) == raw)
            l = mid;
        else
            r = mid;
    }
    askMask = vi(m, 1);
    src1 = us[r];
    src2 = vs[r];
    queue <ll> q;
    vector <char> vis(n, false);
    vis[src1] = true; q.push(src1);
    vis[src2] = true; q.push(src2);
    adjT[src1].push_back({ src2, r });
    adjT[src2].push_back({ src1, r });
    askMask[r] = 0;
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (auto [v, id] : adj[u]) {
            if (vis[v] || id <= l) continue;
            vis[v] = true; q.push(v);
            // cerr << u << ' ' << v << '\n';
            adjT[u].push_back({ v, id });
            adjT[v].push_back({ u, id });
            askMask[id] = 0;
        }
    }}
    dep[src2] = 0;
    dfs(src2, (dis+1)/2, dis);
    // for (ll i : askMask) cout << i << ' ';
    // cout << " askMask\n";
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    // for (ll i : ord) cout << toPar[i] << ' ';
    // cout << " par[ord]\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = ord.size();
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(askMask.begin(), askMask.end());
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == raw)
            l = mid;
        else
            r = mid;
    }
    u1 = ord[r];}
    // cout << u1 << " u1\n";
    fill(vis, vis+MAXN, false);
    ord.clear();
    dep[u1] = 0;
    dfs(u1, dis, dis);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    {ll l = -1, r = ord.size();
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask(askMask.begin(), askMask.end());
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == raw)
            l = mid;
        else
            r = mid;
    }
    // cout << "l, r: " << l << ' ' << r << '\n';
    // cout << "ord[l, r]: " << ord[l] << ' ' << ord[r] << '\n';
    u2 = ord[r];}
    // cout << "u1 " << u1 << '\n';
    // cout << "u2 " << u2 << '\n';
    answer(u1, u2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 8 ms 9888 KB Output is correct
3 Correct 78 ms 19708 KB Output is correct
4 Correct 82 ms 19432 KB Output is correct
5 Correct 75 ms 20964 KB Output is correct
6 Correct 76 ms 18396 KB Output is correct
7 Correct 72 ms 18020 KB Output is correct
8 Correct 88 ms 20584 KB Output is correct
9 Correct 75 ms 17728 KB Output is correct
10 Correct 82 ms 19264 KB Output is correct
11 Correct 62 ms 16548 KB Output is correct
12 Correct 84 ms 21684 KB Output is correct
13 Correct 73 ms 21748 KB Output is correct
14 Correct 79 ms 21732 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10328 KB Output is correct
2 Correct 17 ms 12060 KB Output is correct
3 Correct 17 ms 11032 KB Output is correct
4 Correct 57 ms 22040 KB Output is correct
5 Correct 56 ms 21996 KB Output is correct
6 Correct 62 ms 24416 KB Output is correct
7 Correct 58 ms 15492 KB Output is correct
8 Correct 59 ms 22944 KB Output is correct
9 Correct 54 ms 17824 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 8 ms 9616 KB Output is correct
3 Correct 59 ms 17728 KB Output is correct
4 Correct 76 ms 19256 KB Output is correct
5 Correct 56 ms 15792 KB Output is correct
6 Correct 57 ms 15784 KB Output is correct
7 Correct 65 ms 17384 KB Output is correct
8 Correct 57 ms 15840 KB Output is correct
9 Correct 79 ms 19848 KB Output is correct
10 Correct 83 ms 18760 KB Output is correct
11 Correct 83 ms 21344 KB Output is correct
12 Correct 84 ms 21900 KB Output is correct
13 Correct 91 ms 20488 KB Output is correct
14 Correct 66 ms 17208 KB Output is correct
15 Correct 56 ms 15792 KB Output is correct
16 Correct 53 ms 15648 KB Output is correct
17 Correct 85 ms 21116 KB Output is correct
18 Correct 78 ms 22312 KB Output is correct
19 Correct 56 ms 15688 KB Output is correct
20 Correct 72 ms 15936 KB Output is correct
21 Correct 73 ms 18644 KB Output is correct
22 Correct 59 ms 16812 KB Output is correct
23 Correct 71 ms 20256 KB Output is correct
24 Correct 74 ms 21540 KB Output is correct
25 Correct 98 ms 26168 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10072 KB Output is correct
2 Correct 10 ms 9816 KB Output is correct
3 Correct 97 ms 21644 KB Output is correct
4 Correct 92 ms 20968 KB Output is correct
5 Correct 116 ms 22504 KB Output is correct
6 Correct 119 ms 23672 KB Output is correct
7 Correct 104 ms 22836 KB Output is correct
8 Correct 117 ms 22516 KB Output is correct
9 Correct 70 ms 17164 KB Output is correct
10 Correct 82 ms 19036 KB Output is correct
11 Correct 91 ms 20036 KB Output is correct
12 Correct 111 ms 22016 KB Output is correct
13 Correct 116 ms 23084 KB Output is correct
14 Correct 128 ms 23264 KB Output is correct
15 Correct 112 ms 23200 KB Output is correct
16 Correct 90 ms 20464 KB Output is correct
17 Correct 81 ms 19008 KB Output is correct
18 Correct 62 ms 16460 KB Output is correct
19 Correct 77 ms 20768 KB Output is correct
20 Correct 70 ms 17876 KB Output is correct
21 Correct 112 ms 23308 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9816 KB Output is correct
2 Correct 10 ms 10156 KB Output is correct
3 Correct 85 ms 21264 KB Output is correct
4 Correct 90 ms 21308 KB Output is correct
5 Correct 103 ms 22156 KB Output is correct
6 Correct 99 ms 22952 KB Output is correct
7 Correct 92 ms 21456 KB Output is correct
8 Correct 96 ms 21548 KB Output is correct
9 Correct 94 ms 21348 KB Output is correct
10 Correct 119 ms 23208 KB Output is correct
11 Correct 123 ms 23220 KB Output is correct
12 Correct 117 ms 23068 KB Output is correct
13 Correct 77 ms 18072 KB Output is correct
14 Correct 78 ms 18488 KB Output is correct
15 Correct 87 ms 20580 KB Output is correct
16 Correct 88 ms 19068 KB Output is correct
17 Correct 92 ms 19684 KB Output is correct
18 Correct 90 ms 19564 KB Output is correct
19 Correct 108 ms 22000 KB Output is correct
20 Correct 108 ms 22416 KB Output is correct
21 Correct 123 ms 23248 KB Output is correct
22 Correct 117 ms 23000 KB Output is correct
23 Correct 123 ms 23852 KB Output is correct
24 Correct 123 ms 23600 KB Output is correct
25 Correct 120 ms 22748 KB Output is correct
26 Correct 116 ms 23080 KB Output is correct
27 Correct 72 ms 17976 KB Output is correct
28 Correct 73 ms 20180 KB Output is correct
29 Correct 79 ms 21892 KB Output is correct
30 Correct 77 ms 21176 KB Output is correct
31 Correct 80 ms 20188 KB Output is correct
32 Correct 77 ms 20416 KB Output is correct
33 Partially correct 78 ms 21864 KB Output is partially correct
34 Correct 68 ms 19288 KB Output is correct
35 Correct 73 ms 19800 KB Output is correct
36 Correct 81 ms 20884 KB Output is correct
37 Correct 92 ms 20180 KB Output is correct
38 Correct 97 ms 20912 KB Output is correct
39 Correct 110 ms 23796 KB Output is correct
40 Correct 108 ms 24040 KB Output is correct
41 Correct 130 ms 23716 KB Output is correct
42 Correct 106 ms 23196 KB Output is correct