#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
inline bool smin(int &a , int b) { return b < a ? a = b , true : false; }
typedef vector<int> vi;
typedef long long ll;
void find_pair(int N, vi U, vi V, int A, int B) {
int M = U.size();
vector<vi> adj(N);
rep(i , 0 , M) {
adj[U[i]].pb(i);
adj[V[i]].pb(i);
}
// faze 1 : peyda kardan fasele
int len = ask(vi(M)) / A;
// faze 2 : peyda kardane ye yal to masir
int lovelyEdge = -1;
{
int lo = -1 , hi = M - 1;
while (lo != hi - 1) {
int mid = lo + hi >> 1;
vi local(mid + 1 , 1);
local.resize(M);
if (ask(local) != 1ll * A * len)
hi = mid;
else
lo = mid;
}
lovelyEdge = hi;
}
// faze 3 : peyda kardane rasaye chap va rasaye rast va sakhtane deralht chap o rast :
vector<bool> active(N , true);
vi d1(N) , d2(N);
vi edge1, edge2;
auto bfs = [&](int v , vi &d, vi& edge) {
edge.clear();
edge.pb(lovelyEdge);
fill(all(d) , 1e9);
vi q(N);
int L = 0 , R = 0;
assert(active[v]);
d[v] = 0;
q[R++] = v;
while (L < R) {
v = q[L++];
for (auto e : adj[v]) {
int u = V[e] ^ U[e] ^ v;
if (!active[u]) continue;
if (smin(d[u] , d[v] + 1))
q[R++] = u;
if (d[u] == d[v] + 1) {
if (V[e] == u)
swap(U[e] , V[e]);
edge.pb(e);
}
}
}
return;
};
int V1 = V[lovelyEdge];
int V2 = U[lovelyEdge];
bfs(V1 , d1 , edge1);
bfs(V2 , d2 , edge2);
fill(all(active) , false);
rep(i , 0 , N) if (d1[i] < d2[i]) active[i] = true;
bfs(V1 , d1 , edge1);
fill(all(active) , false);
rep(i , 0 , N) if (d2[i] < d1[i]) active[i] = true;
bfs(V2 , d2 , edge2);
// faze 4 : peyd akardan s O t:
auto finder = [&](int root, vi&d , vi & edge) {
ll len2 = -1;
{
vi local(M , 1);
for (auto e : edge) local[e] = 0;
len2 = ask(local);
}
int lo = -1, hi = edge.size() - 1;
while (lo != hi - 1) {
int mid = lo + hi >> 1;
vi local(M , 1);
rep(i , 0 , mid + 1)
local[edge[i]] = 0;
if (ask(local) == len2) hi = mid;
else lo = mid;
}
if (hi == 0) return root;
if (d[U[edge[hi]]] <= d[V[edge[hi]]]) assert(0);
return U[edge[hi]];
};
int S = finder(V1 , d1 , edge1);
int T = finder(V2 , d2 ,edge2);
if (false && A == 1 && B == 2)
assert(d1[S] + 1 + d2[T] <= len);
answer(S , T);
return;
Compilation message
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
highway.cpp: In lambda function:
highway.cpp:110:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo + hi >> 1;
~~~^~~~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:132:8: error: expected '}' at end of input
return;
^
