Submission #1156424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156424		bobo	Highway Tolls (IOI18_highway)	C++20	0 / 100	247 ms	327680 KiB

highway

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

using ll = long long;

int timer = 0;
int tin[130001], pa[130001], id[130001];
int rv[130001];
vector<pair<int, int>> adj[130001];

void dfs(int u, int p) {
    tin[u] = ++timer;
    rv[timer] = u;
    // cout << "dfs: " << u << '\n';
    for (auto& [v, eid] : adj[u]) {
        if (v == p) continue;
        pa[v] = u, id[v] = eid;
        dfs(v, u);
    }
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
    int m = u.size();
    vector<int> w(m, 0);
    ll dist = ask(w) / A;
    for (int i = 0; i < m; i++) {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }
    pa[0] = 0;
    dfs(0, -1);
    // answer(0, n - 1);
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) / 2;
        w = vector<int>(m, 0);
        for (int i = 1; i <= mid; i++) {
            int node = rv[i];
            if (node != 0) w[id[node]] = 1;
        }
        ll res = ask(w);
        if (1LL * B * dist == res) r = mid;
        else l = mid + 1;
    }
    int T = rv[l];
    l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        w = vector<int>(m, 0);
        for (int i = mid; i <= n; i++) {
            int node = rv[i];
            if (node != 0) w[id[node]] = 1;
        }
        ll res = ask(w);
        if (1LL * B * dist == res) l = mid;
        else r = mid - 1;
    }
    int S = rv[l];
    answer(S, T);
}

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