Submission #444303

#	Time	Username	Problem	Language	Result	Execution time	Memory
444303		two_sides	Highway Tolls (IOI18_highway)	C++17	23 / 100	293 ms	10536 KiB

highway

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

using namespace std;

void find_pair(int N, vector<int> U,
vector<int> V, int A, int B) {
    int M = U.size();
    int lo = 0, hi = M - 1;
    vector<int> w(M);
    int init = ask(w), root[2], ans[2];
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        for (int i = 0; i < M; i++)
            w[i] = i <= mi;
        if (ask(w) > init) {
            root[0] = U[mi];
            root[1] = V[mi];
            hi = mi - 1;
        } else lo = mi + 1;
    }
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[U[i]].push_back(i);
        adj[V[i]].push_back(i);
    }
    vector<int> dis[2], vis[2];
    queue<int> que;
    for (int i = 0; i < 2; i++) {
        dis[i].assign(N, -1);
        vis[i].resize(N);
        que.push(root[i]);
        dis[i][root[i]] = 0;
        ans[i] = root[i];
        while (que.size()) {
            int u = que.front(); que.pop();
            for (int e : adj[u]) {
                int v = u ^ U[e] ^ V[e];
                if (dis[i][v] < 0) {
                    dis[i][v] = dis[i][u] + 1;
                    que.push(v);
                }
            }
        }
    }
    vector<int> ord, idx(N);
    for (int i = 0; i < 2; i++) {
        que.push(root[i]);
        vis[i][root[i]] = 1;
        ord.assign(M, -1);
        int cnt = 0;
        while (que.size()) {
            int u = que.front(); que.pop();
            for (int e : adj[u]) {
                int v = u ^ U[e] ^ V[e];
                if (dis[i][v] < dis[i ^ 1][v]) {
                    if (!vis[i][v]) {
                        idx[ord[e] = cnt++] = e;
                        vis[i][v] = 1; que.push(v);
                    } else if (dis[i][v] == dis[i][u] + 1)
                        ord[e] = N;
                } else if (root[0] != U[e] || root[1] != V[e])
                    ord[e] = N;
            }
        }
        lo = 0; hi = cnt - 1;
        while (lo <= hi) {
            int mi = (lo + hi) / 2;
            for (int j = 0; j < M; j++)
                w[j] = ord[j] >= mi;
            if (ask(w) > init) {
                int e = idx[mi];
                if (dis[i][U[e]] > dis[i][V[e]])
                    ans[i] = U[e];
                else ans[i] = V[e];
                lo = mi + 1;
            } else hi = mi - 1;
        }
    }
    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