// In The Name Of God
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
const int MAX_N = (int)1e5 + 7;
const int INF = (int)1e9 + 7;
int n, m, A, B;
vector <int> V, U;
vector < pair <int, int > > g[MAX_N];
namespace Tree {
int depth;
ll min_len;
int dep[MAX_N];
vector <int> e;
bool was[MAX_N];
void bfs(int v = 0, int p = -1, int lvl = 0) {
dep[v] = 0;
was[v] = 1;
queue <int> q;
q.push(v);
while (sz(q)) {
int x = q.front();
q.pop();
for (auto to : g[x]) {
if (!was[to.f]) {
dep[to.f] = dep[x] + 1;
was[to.f] = 1;
q.push(to.f);
if (dep[x] + 1 == depth) {
// e.pb(to.s);
}
}
}
}
/// -------------------------
/*return;
for (auto to : g[v]) {
if (to.f != p) {
dfs(to.f, v, lvl + 1);
if (lvl + 1 == depth) {
e.pb(to.s);
}
}
}*/
}
int id(const vector <int> &x) {
if (sz(x) == 1) return x[0];
int mid = sz(x) / 2;
vector <int> q(m, 0), sol;
rep(i, 0, mid - 1) {
q[x[i]] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
if (cur > min_len) return id(sol);
vector <int> on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return id(on);
}
void solve(int S = 0) {
// if (n != m + 1) return;
{
vector <int> q(m, 0);
min_len = ask(q);
depth = min_len / A;
}
bfs(S);
rep(i, 0, n) {
for (auto to : g[i]) {
if (min(dep[i], dep[to.f]) + 1 == depth) {
e.pb(to.s);
}
}
}
int ed = id(e);
rep(i, 0, n - 1) {
for (auto it : g[i]) {
if (it.s == ed) {
if (dep[i] > dep[it.f]) answer(S, i);
else answer(S, it.f);
return;
}
}
}
assert(0);
}
}
namespace FindS {
int dist;
int dep[MAX_N];
vector <int> edges[MAX_N];
bool was[MAX_N];
void bfs(int v = 0, int p = -1, int lvl = 0) {
dep[v] = 0;
was[v] = 1;
queue <int> q;
q.push(v);
while (sz(q)) {
int x = q.front();
q.pop();
for (auto to : g[x]) {
if (!was[to.f]) {
dep[to.f] = dep[x] + 1;
was[to.f] = 1;
q.push(to.f);
}
}
}
// ------------------------
/*return;
for (auto to : g[v]) {
if (to.f != p) {
dfs(to.f, v, lvl + 1);
edges[lvl].pb(to.s);
}
}*/
}
int id(vector < pair <int, vector <int> > > x) {
if (sz(x) == 1) return x[0].s[0];
int mid = sz(x) / 2;
vector <int> q(m, 0);
vector < pair <int, vector <int> > > sol;
rep(i, 0, mid - 1) {
for (auto it : x[i].s) q[j] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
if (cur > (ll)dist * A) return id(sol);
vector < pair <int, vector <int> > > on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return id(on);
}
bool check(int x) {
vector <int> q(m, 0);
for (auto to : g[x]) q[to.s] = 1;
return ask(q) == (ll)(dist - 1) * A + B;
}
int GetS() {
{
vector <int> q(m, 0);
dist = ask(q) / A;
}
// dist of path
bfs();
rep(i, 0, n) {
for (auto to : g[i]) {
edges[min(dep[i], dep[to.f])].pb(to.s);
}
}
int l = 0, r = n, res = -1;
while (l <= r) {
int mid = l + r >> 1;
vector <int> q(m, 0);
rep(i, 0, mid) for (auto ind : edges[i]) q[ind] = 1;
ll cur = ask(q);
if (cur == (ll)dist * B) res = mid, r = mid - 1;
else l = mid + 1;
}
if (res == -1) {
if (0) cerr << "DIDN't FIND DEPTH of S" << endl;
}
assert(res != -1);
// found depth of S
{
map <int, vector <int > > edge_tov;
for (auto i : edges[res]) {
int x = V[i], y = U[i];
if (dep[x] > dep[y]) swap(x, y);
edge_tov[y].pb(i);
}
vector < pair <int, vector <int > > > X;
for (auto it : edge_tov) {
X.pb(it);
}
int ind = id(X);
if (0) cerr << dep[V[ind]] << ' ' << dep[U[ind]] << endl;
if (check(V[ind])) return V[ind];
return U[ind];
}
// found S
if (0) cerr << "DIDN'T FIND S" << endl;
assert(0);
}
}
void find_pair(int N, vector<int> _U, vector<int> _V, int _A, int _B) {
n = N;
m = sz(_U);
A = _A;
B = _B;
V = _V;
U = _U;
rep(i, 0, m - 1) {
g[V[i]].pb({U[i], i});
g[U[i]].pb({V[i], i});
}
// copy finished
int S = FindS :: GetS();
if (0) cerr << S << endl;
Tree :: solve(S);
return;
answer(0, N - 1);
}
Compilation message
highway.cpp: In function 'int FindS::id(std::vector<std::pair<int, std::vector<int> > >)':
highway.cpp:165:29: error: 'j' was not declared in this scope
for (auto it : x[i].s) q[j] = 1;
^
highway.cpp:165:14: warning: unused variable 'it' [-Wunused-variable]
for (auto it : x[i].s) q[j] = 1;
^~
highway.cpp: In function 'int FindS::GetS()':
highway.cpp:199:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
