oj.uz

Submission #710564

# Submission time Handle Problem Language Result Execution time Memory
710564 2023-03-15T11:09:57 Z Cyanmond Highway Tolls (IOI18_highway) C++17
90 / 100
 290 ms 14800 KB 
#include "highway.h"
#include <bits/stdc++.h>

using i64 = long long;

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    const int M = (int)U.size();
    std::vector<std::vector<std::pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
    }
    // find one of the vertices on the min cost path
    const int distLen = ask(std::vector<int>(M, 0)) / (i64)A;
    auto binarySearch = [&](int ng, int ok, auto &&f) {
        while (std::abs(ok - ng) > 1) {
            const auto mid = (ok + ng) / 2;
            if (f(mid)) ok = mid;
            else ng = mid;
        }
        return ok;
    };
    int root = binarySearch(0, N, [&](const int m) {
        std::vector<int> w(M);
        for (int i = 0; i < M; ++i) {
            const int mx = std::max(U[i], V[i]);
            w[i] = mx < m ? 0 : 1;
        }
        return ask(w) == (i64)(distLen) * A;
    }) - 1;

    // construct BFS-Tree
    std::vector<std::vector<std::pair<int, int>>> bfsTree(N);
    std::vector<int> parent(N, -1);
    std::queue<int> que;
    que.push(root);
    std::vector<bool> isSeen(N);
    isSeen[root] = true;
    std::vector<bool> exTree(M);
    while (not que.empty()) {
        const int f = que.front();
        que.pop();
        for (const auto &[t, i] : graph[f]) {
            if (isSeen[t]) continue;
            isSeen[t] = true;
            bfsTree[f].push_back({t, i});
            exTree[i] = true;
            parent[t] = f;
            que.push(t);
        }
    }

    // Euler-Tour
    std::vector<int> in(N, -1), revIn(N);
    auto dfs = [&](auto &&self, const int v, int &id) -> void {
        revIn[id] = v;
        in[v] = id;
        ++id;
        for (const auto &[t, i] : bfsTree[v]) {
            if (in[t] != -1) continue;
            self(self, t, id);
        }
    };
    int gomi = 0;
    dfs(dfs, root, gomi);
    
    // binary search, find path
    // find r
    int r = binarySearch(0, N, [&](const int m) {
        std::vector<int> w(M, 1);
        for (int i = 0; i < M; ++i) {
            if (not exTree[i]) continue;
            const int mx = std::max(in[U[i]], in[V[i]]);
            w[i] = mx < m ? 0 : 1;
        }
        return ask(w) == (i64)(distLen) * A;
    }) - 1;
    int r2 = revIn[r];
    while (parent[r2] != -1 and in[parent[r2]] != 0) {
        r2 = parent[r2];
    }
    r2 = in[r2];
    int l = binarySearch(0, r2, [&](const int m) {
        std::vector<int> w(M, 1);
        for (int i = 0; i < M; ++i) {
            if (not exTree[i]) continue;
            const int mx = std::max(in[U[i]], in[V[i]]);
            if (mx >= r2) w[i] = 0;
            else w[i] = mx < m ? 0 : 1;
        }
        return ask(w) == (i64)(distLen) * A;
    }) - 1;
    answer(revIn[l], revIn[r]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 21 ms 1608 KB Output is correct
3 Correct 165 ms 12508 KB Output is correct
4 Correct 129 ms 12528 KB Output is correct
5 Correct 137 ms 12572 KB Output is correct
6 Correct 133 ms 12428 KB Output is correct
7 Correct 156 ms 12488 KB Output is correct
8 Correct 140 ms 12436 KB Output is correct
9 Correct 127 ms 12428 KB Output is correct
10 Correct 172 ms 12444 KB Output is correct
11 Correct 157 ms 13676 KB Output is correct
12 Correct 176 ms 13708 KB Output is correct
13 Correct 156 ms 13576 KB Output is correct
14 Correct 183 ms 13328 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1828 KB Output is correct
2 Correct 30 ms 3348 KB Output is correct
3 Correct 34 ms 5072 KB Output is correct
4 Correct 132 ms 14188 KB Output is correct
5 Correct 123 ms 14188 KB Output is correct
6 Correct 87 ms 14568 KB Output is correct
7 Correct 84 ms 14800 KB Output is correct
8 Correct 92 ms 14232 KB Output is correct
9 Correct 101 ms 14492 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 13 ms 1608 KB Output is correct
3 Correct 109 ms 9824 KB Output is correct
4 Correct 152 ms 12444 KB Output is correct
5 Correct 131 ms 12468 KB Output is correct
6 Correct 115 ms 12428 KB Output is correct
7 Correct 134 ms 12432 KB Output is correct
8 Correct 156 ms 12384 KB Output is correct
9 Correct 127 ms 12432 KB Output is correct
10 Correct 163 ms 12444 KB Output is correct
11 Correct 184 ms 13412 KB Output is correct
12 Correct 153 ms 13484 KB Output is correct
13 Correct 175 ms 13508 KB Output is correct
14 Correct 162 ms 13464 KB Output is correct
15 Correct 135 ms 12444 KB Output is correct
16 Correct 133 ms 12436 KB Output is correct
17 Correct 137 ms 13404 KB Output is correct
18 Correct 163 ms 13552 KB Output is correct
19 Correct 154 ms 12436 KB Output is correct
20 Correct 134 ms 13724 KB Output is correct
21 Correct 128 ms 11988 KB Output is correct
22 Correct 106 ms 11972 KB Output is correct
23 Correct 143 ms 11812 KB Output is correct
24 Correct 121 ms 12164 KB Output is correct
25 Correct 136 ms 14048 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1688 KB Output is correct
2 Correct 17 ms 1724 KB Output is correct
3 Correct 189 ms 12828 KB Output is correct
4 Correct 193 ms 13192 KB Output is correct
5 Correct 257 ms 13948 KB Output is correct
6 Correct 290 ms 13936 KB Output is correct
7 Correct 267 ms 13960 KB Output is correct
8 Correct 258 ms 13952 KB Output is correct
9 Correct 158 ms 8140 KB Output is correct
10 Correct 152 ms 8128 KB Output is correct
11 Correct 235 ms 9324 KB Output is correct
12 Correct 224 ms 12168 KB Output is correct
13 Correct 272 ms 12996 KB Output is correct
14 Correct 182 ms 14036 KB Output is correct
15 Correct 261 ms 14068 KB Output is correct
16 Correct 227 ms 9444 KB Output is correct
17 Correct 147 ms 12180 KB Output is correct
18 Correct 165 ms 12516 KB Output is correct
19 Correct 135 ms 12368 KB Output is correct
20 Correct 129 ms 12464 KB Output is correct
21 Correct 216 ms 14180 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1660 KB Output is correct
2 Correct 18 ms 1684 KB Output is correct
3 Partially correct 163 ms 12856 KB Output is partially correct
4 Correct 188 ms 13004 KB Output is correct
5 Correct 210 ms 13192 KB Output is correct
6 Correct 219 ms 13944 KB Output is correct
7 Correct 191 ms 12888 KB Output is correct
8 Correct 154 ms 13040 KB Output is correct
9 Correct 260 ms 13196 KB Output is correct
10 Partially correct 278 ms 13928 KB Output is partially correct
11 Correct 203 ms 13952 KB Output is correct
12 Partially correct 245 ms 13948 KB Output is partially correct
13 Correct 134 ms 9424 KB Output is correct
14 Correct 173 ms 8132 KB Output is correct
15 Correct 165 ms 9332 KB Output is correct
16 Correct 150 ms 8204 KB Output is correct
17 Correct 135 ms 9332 KB Output is correct
18 Correct 195 ms 8208 KB Output is correct
19 Correct 205 ms 12168 KB Output is correct
20 Correct 236 ms 13092 KB Output is correct
21 Correct 260 ms 14052 KB Output is correct
22 Partially correct 217 ms 13992 KB Output is partially correct
23 Correct 238 ms 14052 KB Output is correct
24 Partially correct 251 ms 14032 KB Output is partially correct
25 Correct 227 ms 14248 KB Output is correct
26 Correct 265 ms 14072 KB Output is correct
27 Correct 135 ms 12452 KB Output is correct
28 Correct 117 ms 12200 KB Output is correct
29 Correct 125 ms 12576 KB Output is correct
30 Partially correct 111 ms 12452 KB Output is partially correct
31 Partially correct 117 ms 12364 KB Output is partially correct
32 Correct 121 ms 12156 KB Output is correct
33 Correct 135 ms 12716 KB Output is correct
34 Correct 155 ms 12364 KB Output is correct
35 Partially correct 143 ms 12284 KB Output is partially correct
36 Correct 139 ms 12144 KB Output is correct
37 Partially correct 121 ms 12420 KB Output is partially correct
38 Correct 166 ms 12376 KB Output is correct
39 Correct 196 ms 14300 KB Output is correct
40 Partially correct 261 ms 14416 KB Output is partially correct
41 Correct 243 ms 14172 KB Output is correct
42 Correct 240 ms 14192 KB Output is correct