Submission #571980

#	Time	Username	Problem	Language	Result	Execution time	Memory
571980		elazarkoren	Highway Tolls (IOI18_highway)	C++17	51 / 100	166 ms	20372 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;
int a, b;
vii graph[MAX_N];
pii par[MAX_N];

vi dist[MAX_N];
ll original;

bitset<MAX_N> visited;
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 Dfs(neighbor, node, d + 1);
    }
}

vi edges;
int Solve(int u, int v) {
    for (int i = 0; i < n; i++) dist[i].clear();
    visited.reset();
    Dfs(u, v, 0);
    vi query(m, 1);
    for (int i : edges) query[i] = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) query[par[i].y] = 1;
    }
    query[par[u].y] = 0;
    ll toll = ask(query);
    int d = abs(toll - original) / (b - a);
    fill(all(query), 1);
    for (int i : edges) query[i] = 0;
    vi &options = dist[d];
    int begin = 0, end = options.size(), mid;
    while (begin < end) {
        mid = (begin + end) >> 1;
        for (int i = begin; i <= mid; i++) {
            query[par[options[i]].y] = 1;
        }
        if (ask(query) != original) end = mid;
        else begin = mid + 1;
        for (int i = begin; i <= mid; i++) {
            query[par[options[i]].y] = 0;
        }
    }
    return options[end];
}

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 U, vi V, int A, int B) {
    m = U.size(), n = N;
    a = A, b = B;
    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;
    }
    original = ask(v);
    answer(Solve(U[end], V[end]), Solve(V[end], U[end]));
}
//5 6 4 5 1 4
//0 1
//0 4
//3 4
//1 3
//2 3
//1 2

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