#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=90000+10;
long long n,a,b,aval,s,t;
long long m,sz[maxn],vis[maxn];
vector<long long>adj[maxn];
struct yal{
long long u,v;
long long getad(long long fu){
return (fu^v^u);
}
}alle[maxn];
long long pors(vector<long long>er){
vector<long long>ret(m);
for(auto x:er){
ret[x]=1;
}
return ask(ret);
}
void calsz(long long u,long long par=-1){
sz[u]=1;
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(vis[v]==0&&v!=par){
calsz(v,u);
sz[u]+=sz[v];
}
}
}
long long findcen(long long u,long long szz,long long par=-1){
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(vis[v]==0&&sz[v]*2>szz&&v!=par){
return findcen(v,szz,u);
}
}
return u;
}
long long finds(long long u=0){
// cout<<u<<endl;
calsz(u);
// cout<<u<<endl;
long long v=findcen(u,sz[u]);
// cout<<u<<endl;
vector<long long>tof;
for(auto x:adj[v]){
long long z=alle[x].getad(v);
if(vis[z]==0){
tof.push_back(x);
}
}
long long fake=pors(tof);
if(fake==aval){
return v;
}
long long low=-1,high=(long long)tof.size(),mid;
while(high-low>1){
mid=(high+low)>>1;
vector<long long>ers;
for(long long i=0;i<=mid;i++){
ers.push_back(tof[i]);
}
fake=pors(ers);
if(fake==aval){
low=mid;
}else{
high=mid;
}
}
vis[v]=1;
return finds(alle[tof[high]].getad(v));
}
vector<long long>ham;
long long bal[maxn];
void dfscal(long long u,long long len,long long par=-1,long long now=0){
if(now==len){
ham.push_back(u);
return ;
}
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(v==par){
continue;
}
bal[v]=x;
dfscal(v,len,u,now+1);
}
}
long long findt(){
dfscal(s,aval/a);
long long low=-1,high=(long long)ham.size()-1,mid;
while(high-low>1){
vector<long long>ers;
mid=(high+low)>>1;
for(long long i=0;i<=mid;i++){
ers.push_back(bal[ham[i]]);
}
long long fake=pors(ers);
if(fake==aval){
low=mid;
}else{
high=mid;
}
}
return ham[high];
}
void calc(){
// cout<<"av"<<endl;
// s=finds();
s=0;
// cout<<"dov"<<endl;
t=findt();
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N;
m = U.size();
a=A;
b=B;
for(long long i=0;i<m;i++){
alle[i].u=U[i];
alle[i].v=V[i];
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
if(m!=n-1){
answer(0,1);
return ;
}
aval=pors({});
calc();
//cout<<s<<" "<<t<<endl;
answer(s,t);
}
Compilation message
highway.cpp: In function 'long long int pors(std::vector<long long int>)':
highway.cpp:21:14: error: invalid initialization of reference of type 'const std::vector<int>&' from expression of type 'std::vector<long long int>'
21 | return ask(ret);
| ^~~
In file included from highway.cpp:1:
highway.h:7:39: note: in passing argument 1 of 'long long int ask(const std::vector<int>&)'
7 | long long ask(const std::vector<int> &w);
| ~~~~~~~~~~~~~~~~~~~~~~~~^
