제출 #1317223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317223		starplatinum	통행료 (IOI18_highway)	C++17	100 / 100	134 ms	10424 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    int N, M;
    vector<int> U, V;
    vector<vector<int>> adj;
    vector<int> w;
    long long D0;

    vector<int> bfs(int src) {
        vector<int> dist(N, -1);
        queue<int> q;
        dist[src] = 0;
        q.push(src);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        return dist;
    }

    bool has_edge_prefix(int k) {
        // edges [0..k] light (0), others heavy (1)
        for (int i = 0; i < M; ++i) w[i] = (i <= k ? 0 : 1);
        return ask(w) == D0;
    }

    struct SideSearchContext {
        // side[x] = 0 if closer to u, 1 if closer to v (ties assigned to 0)
        vector<int> side;
        vector<int> ord[2];
        vector<int> pos0, pos1; // positions within ord[0] / ord[1] (only valid for that side)
    };

    bool has_side_prefix(const SideSearchContext& ctx, int targetSide, int k) {
        // Always include ALL vertices of the opposite side.
        // Include first k vertices of targetSide order.
        for (int i = 0; i < M; ++i) {
            int a = U[i], b = V[i];

            auto inSet = [&](int x) -> bool {
                int s = ctx.side[x];
                if (targetSide == 0) {
                    if (s == 1) return true;                // opposite side fully included
                    return ctx.pos0[x] < k;                 // prefix of side 0
                } else {
                    if (s == 0) return true;                // opposite side fully included
                    return ctx.pos1[x] < k;                 // prefix of side 1
                }
            };

            w[i] = (inSet(a) && inSet(b)) ? 0 : 1;
        }
        return ask(w) == D0;
    }

    int find_endpoint_in_side(const SideSearchContext& ctx, int targetSide) {
        const vector<int>& ord = ctx.ord[targetSide];
        int sz = (int)ord.size();

        // We know:
        // k=0 => missing the endpoint on this side => false
        // k=sz => all vertices included => true
        int lo = 0, hi = sz;
        while (hi - lo > 1) {
            int mid = lo + (hi - lo) / 2;
            if (has_side_prefix(ctx, targetSide, mid)) hi = mid;
            else lo = mid;
        }
        return ord[hi - 1];
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
    (void)A; (void)B;

    N = n;
    U = std::move(u);
    V = std::move(v);
    M = (int)U.size();

    adj.assign(N, {});
    adj.reserve(N);
    for (int i = 0; i < M; ++i) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }

    w.assign(M, 0);
    D0 = ask(w); // all light

    // Step 1: find an edge on some shortest S-T path (monotone edge-prefix search).
    int lo = -1, hi = M - 1; // hi is true because hi means all edges light => ask == D0
    while (hi - lo > 1) {
        int mid = lo + (hi - lo) / 2;
        if (has_edge_prefix(mid)) hi = mid;
        else lo = mid;
    }
    int e = hi;
    int u0 = U[e], v0 = V[e];

    // BFS from both endpoints of that edge
    vector<int> distU = bfs(u0);
    vector<int> distV = bfs(v0);

    // Build partition by which endpoint is closer (ties arbitrary)
    SideSearchContext ctx;
    ctx.side.assign(N, 0);
    ctx.ord[0].clear();
    ctx.ord[1].clear();
    ctx.ord[0].reserve(N);
    ctx.ord[1].reserve(N);

    for (int x = 0; x < N; ++x) {
        if (distU[x] < distV[x]) ctx.side[x] = 0;
        else if (distV[x] < distU[x]) ctx.side[x] = 1;
        else ctx.side[x] = 0; // tie -> side 0
        ctx.ord[ctx.side[x]].push_back(x);
    }

    // Sort each side by distance to its anchor, then id
    sort(ctx.ord[0].begin(), ctx.ord[0].end(), [&](int a, int b) {
        if (distU[a] != distU[b]) return distU[a] < distU[b];
        return a < b;
    });
    sort(ctx.ord[1].begin(), ctx.ord[1].end(), [&](int a, int b) {
        if (distV[a] != distV[b]) return distV[a] < distV[b];
        return a < b;
    });

    ctx.pos0.assign(N, INT_MAX);
    ctx.pos1.assign(N, INT_MAX);
    for (int i = 0; i < (int)ctx.ord[0].size(); ++i) ctx.pos0[ctx.ord[0][i]] = i;
    for (int i = 0; i < (int)ctx.ord[1].size(); ++i) ctx.pos1[ctx.ord[1][i]] = i;

    // Step 2+3: find one endpoint in each side (total queries <= log|side0| + log|side1| <= 32)
    int a = find_endpoint_in_side(ctx, 0);
    int b = find_endpoint_in_side(ctx, 1);

    answer(a, b);
}

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