#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e6 + 10;
bool bad[MAXN];
int askcnt = 0;
ll from[MAXN], to[MAXN], n, m, par[MAXN], mn;
vector<int> adj[MAXN], dfs_order, fuck, jahel;
ll fucking_root, A, B;
inline int f(int ind, int v) {
return from[ind] ^ to[ind] ^ v;
}
void dfs(int v, int p, int d = 0) {
dfs_order.push_back(v);
if (d == mn / A)
jahel.push_back(v);
for (int ind : adj[v]) {
int u = f(ind, v);
if (u == p) continue;
if (bad[u]) continue;
par[u] = ind;
dfs(u, v, d + 1);
}
}
inline vector<int> seg(int l, int r) {
vector<int> ans;
for (int i = l; i <= r; i++)
ans.push_back(par[dfs_order[i]]);
return ans;
}
inline int get(vector<int> vec) {
askcnt++;
assert(askcnt <= 90);
vector<int32_t> W(m);
for (int i = 0; i < m; i++) W[i] = 1;
for (int e : fuck)
W[e] = 0;
for (int e : vec)
W[e] = 1;
return ask(W);
}
inline int getp(vector<int> vec) {
askcnt++;
assert(askcnt <= 90);
vector<int32_t> W(m);
for (int i = 0; i < m; i++)
W[i] = 1;
for (int e : vec)
W[e] = 0;
return ask(W);
}
inline int get(int l, int r) {
return get(seg(l, r));
}
inline int getp(int l, int r) {
return getp(seg(l, r));
}
inline int find(int root, int tof = 0) {
par[root] = -1;
dfs_order.clear();
jahel.clear();
dfs(root, root);
debug(root)
jahel.insert(jahel.begin(), 0);
int l = 1, r = int(dfs_order.size()) - 1;
//tof = 0;
if (tof) r = int(jahel.size()) - 1;
for (int e : dfs_order) cerr << e << sep;
cerr << endl;
while (l < r) {
int mid = (l + r) >> 1;
int tmid = mid;
if (tof) {
tmid = find(all(dfs_order), jahel[mid]) - dfs_order.begin();
assert(tmid < dfs_order.size());
}
if (getp(1, tmid) == mn) r = mid;
else l = mid + 1;
}
return (tof ? jahel[l] : dfs_order[l]);
}
int dist[MAXN];
const double Z = 0.45;
inline vector<int> random_spt() {
vector<int> ans;
queue<int> q;
int l = 0, r = n - 1;
while (l < r) {
int len = r - l;
int mid = l + Z * len;
mid = max(mid, l);
mid = min(mid, r - 1);
vector<int32_t> W(m);
for (int i = 0; i < m; i++)
if (from[i] <= mid || to[i] <= mid)
W[i] = 1;
if (ask(W) == mn) {
for (int i = l; i <= mid; i++) bad[i] = true;
l = mid + 1;
} else r = mid;
}
int v = l;
fucking_root = v;
memset(dist, 63, sizeof dist);
q.push(v);
dist[v] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
if (v < fucking_root) continue;
for (int ind : adj[v]) {
int u = f(ind, v);
if (u < fucking_root) continue;
if (dist[u] > dist[v] + 1) {
dist[u] = dist[v] + 1;
q.push(u);
ans.push_back(ind);
}
}
}
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A_, int B_) {
m = U.size();
n = N;
A = A_;
B = B_;
for (int i = 0; i < m; i++) {
from[i] = U[i];
to[i] = V[i];
adj[from[i]].push_back(i);
adj[to[i]].push_back(i);
}
for (int i = 0; i < m; i++)
fuck.push_back(i);
mn = get({});
vector<int> tmp = random_spt();
fuck = tmp;
for (int i = 0; i < n; i++) adj[i].clear();
for (int ind : tmp) {
adj[from[ind]].push_back(ind);
adj[to[ind]].push_back(ind);
}
int v = find(fucking_root);
int u = find(v, 1);
cerr << u << sep << v << endl;
answer(u, v);
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from highway.cpp:2:
highway.cpp: In function 'll find(ll, ll)':
highway.cpp:107:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | assert(tmid < dfs_order.size());
| ~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cchuvKwa.o: in function `main':
grader.cpp:(.text.startup+0x16c): undefined reference to `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status
