Submission #710554

#	Time	Username	Problem	Language	Result	Execution time	Memory
710554		Cyanmond	Highway Tolls (IOI18_highway)	C++17	72 / 100	243 ms	14792 KiB

highway

#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)) / 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);
        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);
        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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 21 / 31