Submission #572020

#	Time	Username	Problem	Language	Result	Execution time	Memory
572020		elazarkoren	Highway Tolls (IOI18_highway)	C++17	51 / 100	257 ms	22824 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e5;

int n, m;
vii graph[MAX_N];
pii par[MAX_N];
int U[MAX_N], V[MAX_N];

vi dist[MAX_N];

bitset<MAX_N> visited;
vi curr_edges;
void Dfs(int node, int parent, int d) {
    dist[d].push_back(node);
    visited[node] = true;
    par[node].x = parent;
    for (auto [neighbor, ind] : graph[node]) {
        if (neighbor == parent) par[node].y = ind;
        else {
            curr_edges.push_back(ind);
            Dfs(neighbor, node, d + 1);
        }
    }
}

ll original = 0;

vi edges;
int Solve(int u, int v) {
    for (int i = 0; i < n; i++) dist[i].clear();
    visited.reset();
    curr_edges.clear();
    Dfs(u, v, 0);
    vi query(m, 1);
    for (int i : edges) query[i] = 0;
    for (int i : curr_edges) query[i] = 1;
    int begin = 0, end = curr_edges.size(), mid;
    while (begin < end) {
        mid = (begin + end) >> 1;
        for (int i = 0; i < mid; i++) {
            query[curr_edges[i]] = 0;
        }
        if (ask(query) != original) begin = mid + 1;
        else end = mid;
        for (int i = 0; i < mid; i++) {
            query[curr_edges[i]] = 1;
        }
    }
    if (!end) return u;
    int i = curr_edges[end - 1];
    return par[U[i]].x == V[i] ? U[i] : V[i];
}

vii Bfs(int node) {
    vii dists(n, {n, -1});
    dists[node] = {0, -1};
    queue<int> q;
    q.push(node);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto [u, i] : graph[v]) {
            if (dists[v].x + 1 < dists[u].x) {
                dists[u] = {dists[v].x + 1, i};
                q.push(u);
            }
        }
    }
    return dists;
}

void find_pair(int N, vi U1, vi V1, int A, int B) {
    m = U1.size(), n = N;
    for (int i = 0; i < m; i++) {
        U[i] = U1[i], V[i] = V1[i];
    }
    for (int i = 0; i < m; i++) {
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
    }
    original = ask(vi(m));
    int begin = 0, end = m, mid;
    while (begin < end) {
        mid = (begin + end) >> 1;
        vi v(m);
        fill(v.begin(), v.begin() + mid + 1, 1);
        if (ask(v) > original) end = mid;
        else begin = mid + 1;
    }
    int x = V[end], y = U[end];
    vii d1 = Bfs(x), d2 = Bfs(y);
    d1[x].y = end, d2[y].y = end;
    for (int i = 0; i < n; i++) {
        if (i == y) continue;
        if (d1[i].x < d2[i].x) {
            edges.push_back(d1[i].y);
        } else if (d1[i].x > d2[i].x){
            edges.push_back(d2[i].y);
        }
    }
    for (int i = 0; i < n; i++) graph[i].clear();
    vi v(m, 1);
    for (int i : edges) {
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
        v[i] = 0;
    }
    answer(Solve(U[end], V[end]), Solve(V[end], U[end]));
}

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