#include "highway.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N=90005;
int q;
int remedges;
int n,m;
vector<int>w;
vector<pair<int,int> >g[MAX_N],G[MAX_N];
long long edges,cost;
int root;
int a,b;
int parent[MAX_N];
int paredge[MAX_N];
int depth[MAX_N];
vector<int>ENDS;
vector<pair<int,int>>nodes;
bool used[MAX_N];
bool usededge[130010];
void initbfs()
{
queue<int>q;
q.push(root);
used[root]=1;
while(q.size())
{
int u=q.front();
q.pop();
for(auto [v,edge]:G[u])
{
if(used[v])continue;
used[v]=1;
usededge[edge]=1;
g[u].push_back({v,edge});
g[v].push_back({u,edge});
parent[v]=u;
paredge[v]=edge;
depth[v]=depth[u]+1;
q.push(v);
}
}
}
int onpath()
{
int l=0,r=n-1;
int ans;
while(l<=r)
{
int mid=(l+r)/2;
for(int u=0;u<=mid;u++)
{
for(auto [v,edge]:G[u])
{
w[edge]=1;
}
}
long long ncost=ask(w);q++;
for(int u=0;u<=mid;u++)
{
for(auto [v,edge]:G[u])
{
w[edge]=0;
}
}
if(ncost!=cost)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
void nodesdfs(int u)
{
if(depth[u]>remedge)return;
nodes.push_back({depth[u],u});
for(auto [v,edge]:g[u])
{
if(v==parent[u])continue;
nodesdfs(v);
}
}
int rec(int l,int r)
{
if(l==r)
{
return nodes[l].second;
}
int mid=(l+r)/2;
for(int i=l;i<=mid;i++)
{
w[paredge[nodes[i].second]]=1;
}
long long ncost=ask(w);q++;
for(int i=l;i<=mid;i++)
{
w[paredge[nodes[i].second]]=0;
}
if(ncost!=cost)return rec(l,mid);
return rec(mid+1,r);
}
void solve(int branch,bool with)
{
nodes.clear();
for(int i=0;i<g[root].size();i++)
{
if(with)
{
if(i!=branch)continue;
}
else
{
if(i==branch)continue;
}
nodesdfs(g[root][i].first);
}
sort(nodes.rbegin(),nodes.rend());
ENDS.push_back(rec(0,nodes.size()-1));
}
int solvetwo()
{
int l=0,r=g[root].size()-1;
int ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
for(int i=0;i<=mid;i++)
{
w[g[root][i].second]=1;
}
long long ncost=ask(w);q++;
for(int i=0;i<=mid;i++)
{
w[g[root][i].second]=0;
}
if(ncost!=cost)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
n=N;
m=U.size();
w.resize(m);
a=A;
b=B;
for(int i=0;i<m;i++)
{
G[U[i]].push_back({V[i],i});
G[V[i]].push_back({U[i],i});
}
cost=ask(w);q++;
edges=cost/a;
remedges=edges;
root=onpath();
initbfs();
for(int i=0;i<m;i++)
{
if(usededge[i])continue;
w[i]=1;
}
int branch=solvetwo();
solve(branch,1);
if(depth[ENDS[0]]==edges)
{
ENDS.push_back(root);
}
else
{
remedges-=depth[ENDS[0]];
solve(branch,0);
}
if(q>56)while(1);
answer(ENDS[0],ENDS[1]);
}
Compilation message
highway.cpp: In function 'void initbfs()':
highway.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for(auto [v,edge]:G[u])
| ^
highway.cpp: In function 'int onpath()':
highway.cpp:59:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | for(auto [v,edge]:G[u])
| ^
highway.cpp:67:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for(auto [v,edge]:G[u])
| ^
highway.cpp: In function 'void nodesdfs(int)':
highway.cpp:84:17: error: 'remedge' was not declared in this scope; did you mean 'remedges'?
84 | if(depth[u]>remedge)return;
| ^~~~~~~
| remedges
highway.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
86 | for(auto [v,edge]:g[u])
| ^
highway.cpp: In function 'void solve(int, bool)':
highway.cpp:118:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i=0;i<g[root].size();i++)
| ~^~~~~~~~~~~~~~~
