Submission #421262

#	Time	Username	Problem	Language	Result	Execution time	Memory
421262		timmyfeng	Highway Tolls (IOI18_highway)	C++17	23 / 100	358 ms	10028 KiB

highway

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

#include "highway.h"

const int N = 90000;

int order[N], where[N], color[N], dist[2][N], ans[2], n;
vector<int> adj[N];

void bfs(int s, int *level) {
    fill(level, level + n, -1);
    level[s] = 0;

    queue<int> que;
    que.push(s);

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto c : adj[u]) {
            if (level[c] == -1) {
                level[c] = level[u] + 1;
                que.push(c);
            }
        }
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
    ::n = n;
    int m = u.size();
    int d = ask(vector<int>(m));

    for (int i = 0; i < m; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    int low = 0, high = m - 1;
    while (low < high) {
        int mid = (low + high) / 2;

        vector<int> traffic(m);
        for (int i = 0; i <= mid; ++i) {
            traffic[i] = true;
        }

        long long cost = ask(traffic);
        if (cost > d) {
            high = mid;
        } else {
            assert(cost == d);
            low = mid + 1;
        }
    }

    int bridge = low;
    bfs(u[bridge], dist[0]);
    bfs(v[bridge], dist[1]);

    for (int i = 0; i < n; ++i) {
        if (dist[0][i] < dist[1][i]) {
            color[i] = 0;
        } else {
            color[i] = 1;
        }
    }

    for (int k = 0; k < 2; ++k) {
        int nk = 0;
        for (int i = 0; i < n; ++i) {
            if (color[i] == k) {
                order[nk++] = i;
            }
        }

        sort(order, order + nk, [&](int a, int b) {
            return dist[k][a] < dist[k][b];
        });

        for (int i = 0; i < nk; ++i) {
            where[order[i]] = i;
        }

        low = 0, high = nk - 1;
        while (low < high) {
            int mid = (low + high) / 2;

            vector<int> traffic(m);
            for (int i = 0; i < m; ++i) {
                if (i == bridge) {
                    traffic[i] = false;
                } else if (color[u[i]] != color[v[i]]) {
                    traffic[i] = true;
                } else if (dist[color[u[i]]][u[i]] == dist[color[v[i]]][v[i]]) {
                    traffic[i] = true;
                } else if (color[u[i]] != k) {
                    traffic[i] = false;
                } else if (max(where[u[i]], where[v[i]]) <= mid) {
                    traffic[i] = false;
                } else {
                    traffic[i] = true;
                }
            }

            long long cost = ask(traffic);
            if (cost > d) {
                low = mid + 1;
            } else {
                assert(cost == d);
                high = mid;
            }
        }

        ans[k] = order[low];
    }

    answer(ans[0], ans[1]);
}

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