#include "highway.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r) {
return uniform_int_distribution <int> (l, r) (rng);
}
vector <pair <int, int>> adj[MAXN];
vector <int> ett, ett2;
int in[MAXN], out[MAXN], dep[MAXN], tt;
void dfs (int pos, int par) {
in[pos] = ++tt;
for (auto j : adj[pos]) {
if (j.first == par) continue;
ett.push_back(j.second);
dep[j.first] = 1 + dep[pos];
dfs(j.first, pos);
}
out[pos] = tt;
}
void dfs2 (int pos) {
for (auto j : adj[pos]) {
if (in[j.first] < in[pos]) continue;
ett2.push_back(j.second);
dfs2(j.first);
}
}
void find_pair (int n, vector <int> u, vector <int> v, int a, int b) {
for (int i = 0; i + 1 < n; i++) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
vector <int> g(n - 1);
ll U = ask(g);
dfs(0, -1);
for (int i = 0; i < n - 1; i++) {
if (dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
}
int l = 0, r = n - 2, p1 = -1;
while (l <= r) {
int mid = (l + r) / 2;
g.clear(); g.resize(n - 1);
for (auto &i : g) i = 0;
for (int j = 0; j <= mid; j++) g[ett[j]] = 1;
ll V = ask(g);
if (V != U) {
r = mid - 1; p1 = mid;
} else {
l = mid + 1;
}
}
l = 0, r = n - 2; int p2 = -1;
while (l <= r) {
int mid = (l + r) / 2;
g.clear(); g.resize(n - 1);
for (auto &i : g) i = 0;
for (int j = mid; j + 1 < n; j++) g[ett[j]] = 1;
ll V = ask(g);
if (V != U) {
l = mid + 1; p2 = mid;
} else {
r = mid - 1;
}
}
p1 = ett[p1]; p2 = ett[p2];
if (in[v[p1]] <= in[v[p2]] && out[v[p2]] <= out[v[p1]]) {
assert(0);
answer(u[p1], v[p2]);
return;
}
dfs2(v[p1]);
l = 0, r = (int)ett2.size() - 1; int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
g.clear(); g.resize(n - 1);
for (auto &i : g) i = 0;
for (int i = mid; i < (int)ett2.size() - 1; i++) {
g[ett2[i]] = 1;
}
ll V = ask(g);
if (V != U) {
l = mid + 1; ans = mid;
} else {
r = mid - 1;
}
}
answer(v[ans], v[p2]);
}
Compilation message
/usr/bin/ld: /tmp/cccEw6VY.o: in function `ask(std::vector<int, std::allocator<int> > const&)':
grader.cpp:(.text+0xa0): multiple definition of `ask(std::vector<int, std::allocator<int> > const&)'; /tmp/ccmhnitW.o:highway.cpp:(.text+0x220): first defined here
/usr/bin/ld: /tmp/cccEw6VY.o: in function `answer(int, int)':
grader.cpp:(.text+0x210): multiple definition of `answer(int, int)'; /tmp/ccmhnitW.o:highway.cpp:(.text+0x270): first defined here
/usr/bin/ld: /tmp/cccEw6VY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccmhnitW.o:highway.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
