oj.uz

Submission #1057608

# Submission time Handle Problem Language Result Execution time Memory
1057608 2024-08-14T00:06:45 Z efishel Highway Tolls (IOI18_highway) C++17
90 / 100
 138 ms 26872 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) {
    vis[u] = true;
    for (auto [v, id] : adjT[u]) {
        if (vis[v]) continue;
        dep[v] = dep[u]+1;
        dfs(v);
        toPar[v] = id;
    }
    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);
    // 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);
    {vll nord;
    for (ll i : ord)
        if (dep[i] == dis) nord.push_back(i);
    swap(ord, nord);}
    // 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 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1 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 1 ms 8536 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 2 ms 8536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8644 KB Output is correct
2 Correct 8 ms 9892 KB Output is correct
3 Correct 87 ms 20128 KB Output is correct
4 Correct 79 ms 20120 KB Output is correct
5 Correct 87 ms 21140 KB Output is correct
6 Correct 79 ms 18420 KB Output is correct
7 Correct 81 ms 17892 KB Output is correct
8 Correct 102 ms 21220 KB Output is correct
9 Correct 71 ms 18092 KB Output is correct
10 Correct 81 ms 19464 KB Output is correct
11 Correct 60 ms 16764 KB Output is correct
12 Correct 80 ms 22164 KB Output is correct
13 Correct 80 ms 22436 KB Output is correct
14 Correct 96 ms 22660 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10328 KB Output is correct
2 Correct 14 ms 12272 KB Output is correct
3 Correct 19 ms 11032 KB Output is correct
4 Correct 58 ms 22440 KB Output is correct
5 Correct 54 ms 22568 KB Output is correct
6 Correct 57 ms 25016 KB Output is correct
7 Correct 48 ms 15628 KB Output is correct
8 Correct 58 ms 23396 KB Output is correct
9 Correct 53 ms 18216 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 9776 KB Output is correct
3 Correct 54 ms 18444 KB Output is correct
4 Correct 77 ms 19880 KB Output is correct
5 Correct 58 ms 15780 KB Output is correct
6 Correct 69 ms 15788 KB Output is correct
7 Correct 65 ms 17952 KB Output is correct
8 Correct 64 ms 15944 KB Output is correct
9 Correct 84 ms 20512 KB Output is correct
10 Correct 87 ms 18868 KB Output is correct
11 Correct 87 ms 21988 KB Output is correct
12 Correct 86 ms 22500 KB Output is correct
13 Correct 76 ms 20892 KB Output is correct
14 Correct 71 ms 17504 KB Output is correct
15 Correct 54 ms 15780 KB Output is correct
16 Correct 56 ms 15632 KB Output is correct
17 Correct 84 ms 21720 KB Output is correct
18 Correct 90 ms 22832 KB Output is correct
19 Correct 58 ms 15692 KB Output is correct
20 Correct 54 ms 15936 KB Output is correct
21 Correct 66 ms 19064 KB Output is correct
22 Correct 62 ms 16816 KB Output is correct
23 Correct 73 ms 21024 KB Output is correct
24 Correct 81 ms 21728 KB Output is correct
25 Correct 109 ms 26872 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9876 KB Output is correct
2 Correct 10 ms 10072 KB Output is correct
3 Correct 92 ms 21692 KB Output is correct
4 Correct 96 ms 21596 KB Output is correct
5 Correct 112 ms 22916 KB Output is correct
6 Correct 138 ms 23696 KB Output is correct
7 Correct 129 ms 23424 KB Output is correct
8 Correct 114 ms 22984 KB Output is correct
9 Correct 79 ms 17196 KB Output is correct
10 Correct 83 ms 19272 KB Output is correct
11 Correct 96 ms 20028 KB Output is correct
12 Correct 112 ms 22580 KB Output is correct
13 Correct 116 ms 23080 KB Output is correct
14 Correct 122 ms 23592 KB Output is correct
15 Correct 119 ms 23588 KB Output is correct
16 Correct 110 ms 20372 KB Output is correct
17 Correct 74 ms 19212 KB Output is correct
18 Correct 62 ms 16596 KB Output is correct
19 Correct 88 ms 21404 KB Output is correct
20 Correct 81 ms 17992 KB Output is correct
21 Correct 108 ms 24108 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10072 KB Output is correct
2 Correct 10 ms 10072 KB Output is correct
3 Correct 99 ms 21760 KB Output is correct
4 Correct 91 ms 21668 KB Output is correct
5 Correct 109 ms 22336 KB Output is correct
6 Correct 132 ms 23392 KB Output is correct
7 Correct 94 ms 21708 KB Output is correct
8 Correct 104 ms 21956 KB Output is correct
9 Correct 105 ms 21896 KB Output is correct
10 Correct 125 ms 23348 KB Output is correct
11 Correct 123 ms 23680 KB Output is correct
12 Correct 123 ms 23576 KB Output is correct
13 Correct 75 ms 18108 KB Output is correct
14 Correct 74 ms 18540 KB Output is correct
15 Correct 89 ms 20616 KB Output is correct
16 Correct 84 ms 19328 KB Output is correct
17 Correct 102 ms 19980 KB Output is correct
18 Correct 87 ms 19744 KB Output is correct
19 Correct 115 ms 22396 KB Output is correct
20 Correct 120 ms 23092 KB Output is correct
21 Correct 112 ms 23596 KB Output is correct
22 Correct 129 ms 23592 KB Output is correct
23 Correct 130 ms 23852 KB Output is correct
24 Correct 127 ms 23724 KB Output is correct
25 Correct 116 ms 23296 KB Output is correct
26 Correct 113 ms 23592 KB Output is correct
27 Correct 78 ms 17968 KB Output is correct
28 Correct 77 ms 20180 KB Output is correct
29 Correct 72 ms 22440 KB Output is correct
30 Correct 91 ms 21872 KB Output is correct
31 Correct 78 ms 20440 KB Output is correct
32 Correct 80 ms 20952 KB Output is correct
33 Partially correct 84 ms 22508 KB Output is partially correct
34 Correct 71 ms 19560 KB Output is correct
35 Correct 74 ms 19884 KB Output is correct
36 Partially correct 85 ms 21520 KB Output is partially correct
37 Correct 76 ms 20684 KB Output is correct
38 Correct 93 ms 21724 KB Output is correct
39 Correct 124 ms 24536 KB Output is correct
40 Correct 123 ms 24616 KB Output is correct
41 Correct 112 ms 24052 KB Output is correct
42 Correct 111 ms 23872 KB Output is correct