제출 #426426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
426426		KoD	통행료 (IOI18_highway)	C++17	51 / 100	249 ms	10920 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

template <class T> using Vec = std::vector<T>;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator() (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

void find_pair(int N, Vec<int> U, Vec<int> V, int A, int B) {
    const int M = (int) U.size();
    assert(M == N - 1);
    Vec<Vec<std::pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        graph[U[i]].emplace_back(V[i], i);
        graph[V[i]].emplace_back(U[i], i);
    }
    Vec<int> pedge(N, -1);
    RecLambda([&](auto&& dfs, const int u) -> void {
        for (const auto [v, e] : graph[u]) {
            if (e != pedge[u]) {
                pedge[v] = e;
                dfs(v);
            }
        }
    })(0);
    const long long len = ask(Vec<int>(M, 0));
    Vec<int> cand(N - 1);
    std::iota(cand.begin(), cand.end(), 1);
    const auto find = [&] {
        while (cand.size() > 1) {
            const int half = (int) cand.size() / 2;
            Vec<int> left(cand.begin(), cand.begin() + half);
            Vec<int> right(cand.begin() + half, cand.end());
            Vec<int> vec(M, 0);
            for (const int u : left) {
                vec[pedge[u]] = 1;
            }
            if (ask(vec) > len) {
                cand = std::move(left);
            } else {
                cand = std::move(right);
            }
        }
        return cand[0];
    };
    const int root = find();
    Vec<int> group(N, 0);
    RecLambda([&](auto&& dfs, const int u) -> void {
        if (u != root) {
            group[u] = 1;
        }
        for (const auto [v, e] : graph[u]) {
            if (e != pedge[u]) {
                dfs(v);
            }
        }
    })(root);
    const auto [upper, lower] = [&] {
        Vec<int> vec(M, 0);
        for (int i = 1; i < N; ++i) {
            vec[pedge[i]] = group[i];
        }
        const long long rsp = ask(vec);
        const int tmp = (rsp - len) / (B - A);
        return std::pair<int, int>(len / A - tmp, tmp);
    }();
    // std::cerr << root << ' ' << upper << ' ' << lower << std::endl;
    Vec<int> depth(N);
    std::fill(pedge.begin(), pedge.end(), -1);
    RecLambda([&](auto&& dfs, const int u) -> void {
        for (const auto [v, e] : graph[u]) {
            if (e != pedge[u]) {
                depth[v] = depth[u] + 1;
                pedge[v] = e;
                dfs(v);
            }
        }
    })(root);
    const int S = [&] {
        cand.clear();
        for (int i = 0; i < N; ++i) {
            if (depth[i] == upper and group[i] == 0) {
                cand.push_back(i);
            }
        }
        return find();
    }();
    const int T = [&] {
        if (lower == 0) {
            return root;
        }
        cand.clear();
        for (int i = 0; i < N; ++i) {
            if (depth[i] == lower and group[i] == 1) {
                cand.push_back(i);
            }
        }
        return find();
    }();
    answer(S, T);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31