#include "highway.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long
using namespace std;
ll l, r, mid, a, b, s, q, rt, P[90000], E[90000];
bool visited[90000];
vector <ll> X;
vector <array<ll, 2> > adj[90000];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
ll M = U.size();
queue <ll> Q;
for (int i=0; i<M; ++i) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
vector <int> W(M), Z(M);
for (int i=0; i<M; ++i) W[i] = 0, Z[i] = 1;
s = ask(W);
l = 0, r = N-1;
while (l < r) {
mid = (l+r)/2;
for (int i=0; i<M; ++i) W[i] = 0;
for (int i=0; i<=mid; ++i) {
for (auto [u, x] : adj[i]) W[x] = 1;
}
q = ask(W);
if (q > s) r = mid;
else l = mid+1;
}
rt = l;
Q.push(rt);
visited[rt] = 1;
while (!Q.empty()) {
auto u = Q.front();
Q.pop();
X.push_back(u);
for (auto [v, x] : adj[u]) {
if (!visited[v] && v >= rt) {
Z[x] = 0, visited[v] = 1, E[v] = x, P[v] = u;
Q.push(v);
}
}
}
reverse(X.begin(), X.end());
X.pop_back();
l = 0, r = X.size()-1;
while (l < r) {
mid = (l+r)/2;
for (int i=0; i<M; ++i) W[i] = Z[i];
for (int i=mid; i>=0; --i) {
if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
}
q = ask(W);
if (q > s) r = mid;
else l = mid+1;
}
a = l;
l = a+1, r = X.size();
while (l < r) {
mid = (l+r)/2;
for (int i=0; i<M; ++i) W[i] = Z[i];
for (int i=mid; i>=0; --i) {
if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
}
q = ask(W);
if (q > s+B-A) r = mid;
else l = mid+1;
}
if (l == X.size()) answer(rt, X[a]);
else answer(X[a], X[l]);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:3: error: 'reverse' was not declared in this scope
49 | reverse(X.begin(), X.end());
| ^~~~~~~
highway.cpp:74:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (l == X.size()) answer(rt, X[a]);
| ~~^~~~~~~~~~~
