#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 100000;
vector<pi>tree[sz+5];
int visited[sz+5];
int parent_a[sz+5],parent_b[sz+5];
int dist_a[sz+5],dist_b[sz+5];
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
int m = U.size();
for(int i=0; i<U.size(); i++){
int a = U[i],b = V[i];
tree[a].emplace_back(pi(b,i));
tree[b].emplace_back(pi(a,i));
}
vector<int>w(m,0);
ll d = ask(w);
int l = 0,r = m-2;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[i] = 1;
if(ask(w)==d) l = M+1;
else r = M-1;
for(int i=0; i<=M; i++) w[i] = 0;
}
int e = l;
int a = U[e],b = V[e];
for(int i=0; i<n; i++) dist_a[i] = dist_b[i] = -1;
dist_a[a] = 0; parent_a[a] = e;
queue<int>q; q.push(a);
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(dist_a[nxt] == -1){
dist_a[nxt] = dist_a[cur] + 1;
parent_a[nxt] = id;
q.push(nxt);
}
}
}
dist_b[b] = 0; parent_b[b] = e;
q.push(b);
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(dist_b[nxt] == -1){
dist_b[nxt] = dist_b[cur] + 1;
parent_b[nxt] = id;
q.push(nxt);
}
}
}
vector<pi>c1,c2;
for(int i=0; i<n; i++){
if(dist_a[i] < dist_b[i]) c1.emplace_back(pi(i,parent_a[i]));
}
sort(c1.begin(),c1.end(),[&](const pi&x,const pi&y){
return dist_a[x.first] > dist_a[y.first];
})
for(int i=0; i<n; i++){
if(dist_b[i] < dist_a[i]) c2.emplace_back(pi(i,parent_b[i]));
}
sort(c2.begin(),c2.end(),[&](const pi&x,const pi&y){
return dist_b[x.first] > dist_b[y.first];
})
for(int i=0; i<m; i++) w[i] = 1;
for(pi p : c1) w[p.second] = 0;
for(pi p : c2) w[p.second] = 0;
l = 0,r = c1.size()-1;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[c1[i].second] = 1;
if(ask(w) > d) r = M-1;
else l = M+1;
for(int i=0; i<=M; i++) w[c1[i].second] = 0;
}
a = c1[l].first;
l = 0,r = c2.size()-1;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[c2[i].second] = 1;
if(ask(w) > d) r = M-1;
else l = M+1;
for(int i=0; i<=M; i++) w[c2[i].second] = 0;
}
b = c2[l].first;
answer(a,b);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i=0; i<U.size(); i++){
| ~^~~~~~~~~
highway.cpp:67:7: error: expected ';' before 'for'
67 | })
| ^
| ;
68 | for(int i=0; i<n; i++){
| ~~~
highway.cpp:68:15: error: 'i' was not declared in this scope
68 | for(int i=0; i<n; i++){
| ^
highway.cpp:73:7: error: expected ';' before 'for'
73 | })
| ^
| ;
74 | for(int i=0; i<m; i++) w[i] = 1;
| ~~~
