#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
#include "highway.h"
using namespace std;
struct Interactive
{
ll f[maxn],n,m,i,u,v,k,s,t,A,B;
vector <int> U,V;
vector <II> a[maxn];
void Init(int _n,int _m,vector <int> _U,vector <int> _V,int _A,int _B,int _s,int _t)
{
n=_n; m=_m; U=_U; V=_V; A=_A; B=_B; s=_s; t=_t;
s++; t++;
for(i=0;i<m;i++) U[i]++,V[i]++;
}
ll Dijkstra(vector <int> status)
{
for(u=1;u<=n;u++) a[u].clear();
for(i=0;i<m;i++)
{
u=U[i]; v=V[i];
if(status[i]==0) k=A; else k=B;
a[u].push_back({ v,k }); a[v].push_back({ u,k });
}
for(u=1;u<=n;u++) f[u]=round(1e18);
set <II> h;
f[s]=0; h.insert({ 0,s });
while(h.size()>0)
{
int u=h.begin()->snd; h.erase(h.begin());
for(II adj:a[u])
{
int v=adj.fst,k=adj.snd;
if(f[v]>f[u]+k)
{
h.erase({ f[v],v });
f[v]=f[u]+k;
h.insert({ f[v],v });
}
}
}
return f[t];
}
} IR;
//ll ask(vector <int> Status) { return IR.Dijkstra(Status); }
//void answer(int s,int t) { cout<<s<<" "<<t<<'\n'; }
vector <int> Deleted;
vector <II> a[maxn];
ll best_cost,best_len;
int fx[maxn],fs[maxn],i,u,v,x,node[maxn];
void find_pair(int n,int m,vector <int> U,vector <int> V,int A,int B)
{
function <ll(vector <int>)> Try_to_Delete=[&](vector <int> Try)
{
vector <int> status(m);
for(int x:Deleted) status[x]=1;
for(int x:Try) status[x]=1;
return ask(status);
};
for(i=0;i<m;i++)
{
u=++U[i]; v=++V[i];
a[u].push_back({ v,i }); a[v].push_back({ u,i });
}
/////////////////////////////////////////////////////////////////////////////////////
//Find x
vector <int> vec;
best_cost=Try_to_Delete(vec);
best_len=best_cost/A;
int l=0,r=m-1,s,t;
while(l<r)
{
int mid=(l+r)>>1;
// cerr<<l<<" "<<r<<" "<<mid<<'\n';
vector <int> vec;
for(i=0;i<=mid;i++) vec.push_back(i);
if(Try_to_Delete(vec)>best_cost) r=mid; else l=mid+1;
}
// cerr<<l<<'\n';
for(i=0;i<l;i++) Deleted.push_back(i);
x=U[l];
////////////////////////////////////////////////////////////////////////////////////
//Find s
auto BFS=[&](int s,int f[])
{
for(int u=1;u<=n;u++) f[u]=round(1e9);
queue <int> q;
q.push(s); f[s]=0;
while(q.size()>0)
{
int u=q.front(); q.pop();
// if(s==2) cerr<<u<<'\n';
for(II adj:a[u])
{
int v=adj.fst,x=adj.snd;
if(f[v]>f[u]+1)
q.push(v),f[v]=f[u]+1;
}
}
};
// cerr<<x<<'\n';
BFS(x,fx);
for(i=1;i<=n;i++) node[i]=i;
sort(node+1,node+n+1,[&](int u,int v){ return fx[u]>fx[v]; });
// for(i=1;i<=n;i++) cerr<<node[i]<<'\n';
l=1; r=n;
while(l<r)
{
int mid=(l+r)>>1;
vector <int> vec;
for(i=1;i<=mid;i++)
{
u=node[i];
for(II adj:a[u])
if(fx[u]==fx[adj.fst]+1) vec.push_back(adj.snd);
}
if(Try_to_Delete(vec)>best_cost) r=mid; else l=mid+1;
}
s=node[l];
///////////////////////////////////////////////////////////////////////////////////////////
//Find t
BFS(s,fs);
// cerr<<fx[2]<<" "<<fx[4]<<" "<<fs[4]<<" "<<best_len<<'\n';
vector <int> candidates;
for(u=1;u<=n;u++)
if(fx[s]+fx[u]==fs[u] && fs[u]==best_len)
candidates.push_back(u);
l=0; r=candidates.size()-1;
while(l<r)
{
int mid=(l+r)>>1;
vector <int> vec;
for(i=0;i<=mid;i++)
{
u=candidates[i];
for(II adj:a[u])
if(fx[u]==fx[adj.fst]+1) vec.push_back(adj.snd);
}
if(Try_to_Delete(vec)>best_cost) r=mid; else l=mid+1;
}
t=candidates[l];
answer(s-1,t-1);
}
/*
int main()
{
freopen("highway.inp","r",stdin);
freopen("highway.out","w",stdout);
int n,m,A,B,s,t,u,v;
vector <int> U,V;
cin>>n>>m>>A>>B>>s>>t;
for(int i=0;i<m;i++) cin>>u>>v,U.push_back(u),V.push_back(v);
IR.Init(n,m,U,V,A,B,s,t);
find_pair(n,m,U,V,A,B);
}
*/
Compilation message
highway.cpp: In lambda function:
highway.cpp:117:31: warning: unused variable 'x' [-Wunused-variable]
117 | int v=adj.fst,x=adj.snd;
| ^
/usr/bin/ld: /tmp/ccRnHRCb.o: in function `main':
grader.cpp:(.text.startup+0x16c): undefined reference to `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status
