Submission #1208688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208688		badge881	Highway Tolls (IOI18_highway)	C++20	100 / 100	120 ms	11336 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    int M = U.size();
    vector<vector<ii>> adj(N);

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

    int64_t all_b = ask(vector<int>(M, 1)),
            all_a = all_b / B * A;

    int lo = -1, hi = M - 1;

    while (hi - lo > 1)
    {
        int mid = (lo + hi) >> 1;
        vector<int> orz(M, 0);
        for (int i = 0; i <= mid; i++)
            orz[i] = 1;
        if (ask(orz) != all_a)
            hi = mid;
        else
            lo = mid;
    }
    int X = U[hi], Y = V[hi], S, T;

    vector<int> depthX(N, INT_MAX), depthY(N, INT_MAX);
    if (1)
    {
        queue<int> q;
        q.push(X);
        depthX[X] = 0;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto [v, idx] : adj[u])
                if (depthX[v] == INT_MAX)
                {
                    depthX[v] = depthX[u] + 1;
                    q.push(v);
                }
        }
    }
    queue<int> q;
    q.push(Y);
    depthY[Y] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto [v, idx] : adj[u])
            if (depthY[v] == INT_MAX)
            {
                depthY[v] = depthY[u] + 1;
                q.push(v);
            }
    }

    vector<int> based(M, 0);

    vector<int> lisX, lisY;

    for (int i = 0; i < N; i++)
        if (depthX[i] != depthY[i])
        {
            if (depthX[i] < depthY[i])
                lisX.emplace_back(i);
            else
                lisY.emplace_back(i);
        }
    for (int i = 0; i < M; i++)
        if ((depthX[U[i]] < depthY[U[i]] and depthX[V[i]] > depthY[V[i]]) or
            (depthX[U[i]] > depthY[U[i]] and depthX[V[i]] < depthY[V[i]]))
            based[i] = 1;

    based[hi] = 0;

    for (int i = 0; i < N; i++)
        if (depthX[i] == depthY[i])
            for (auto [v, idx] : adj[i])
                based[idx] = 1;

    sort(lisX.begin(), lisX.end(), [&](int x, int y)
         { return depthX[x] > depthX[y]; });
    sort(lisY.begin(), lisY.end(), [&](int x, int y)
         { return depthY[x] > depthY[y]; });
    if (1)
    {
        int lo = -1, hi = lisX.size() - 1;
        while (hi - lo > 1)
        {
            int mid = (lo + hi) >> 1;
            vector<int> orz = based;
            for (int i = 0; i <= mid; i++)
                for (auto [v, idx] : adj[lisX[i]])
                    orz[idx] = 1;

            if (ask(orz) != all_a)
                hi = mid;
            else
                lo = mid;
        }
        S = lisX[hi];
    }
    if (1)
    {
        int lo = -1, hi = lisY.size() - 1;
        while (hi - lo > 1)
        {
            int mid = (lo + hi) >> 1;
            vector<int> orz = based;
            for (int i = 0; i <= mid; i++)
                for (auto [v, idx] : adj[lisY[i]])
                    orz[idx] = 1;

            if (ask(orz) != all_a)
                hi = mid;
            else
                lo = mid;
        }
        T = lisY[hi];
    }

    answer(S, T);
}

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