#include "highway.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n,m,niv[100005],roots[5];
ll dist,AA,BB,d[3][100005];
int where[100005];
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool inarb[300005],inx[300005];
int IND;
void bfs(int ind)
{
for(int i=0;i<n;i++)
d[ind][i]=1e9;
d[ind][roots[ind]]=0;
queue<int> coada;
coada.push(roots[ind]);
while(!coada.empty())
{
int nod=coada.front();
coada.pop();
for(auto i:muchii[nod])
if(d[ind][i.first]>d[ind][nod]+1)
{
d[ind][i.first]=d[ind][nod]+1;
coada.push(i.first);
}
}
}
ll buildniv(ll nivmax,ll ind)
{
for(int i=0;i<m;i++)
{
if(inarb[i]==0)
{
w[i]=1;
continue;
}
int a=g[i].first,b=g[i].second;
if(max(d[ind][a],d[ind][b])<=nivmax)
w[i]=0;
else
w[i]=1;
}
return ask(w);
}
ll buildx(int ind)
{
for(int i=0;i<m;i++)
{
if(inarb[i]==0)
{
w[i]=1;
continue;
}
int a=g[i].first,b=g[i].second;
if(d[ind][a]<d[ind][b])
swap(a,b);
if(inx[a])
w[i]=0;
else
w[i]=1;
}
return ask(w);
}
bool byniv(int i,int j)
{
int a=max(d[IND][g[i].first],d[IND][g[i].second]);
int b=max(d[IND][g[j].first],d[IND][g[j].second]);
return a<b;
}
int plsfind(int ind)
{
IND=ind;
for(int i=0;i<m;i++)
inarb[i]=0;
for(int i=0;i<n;i++)
d[ind][i]=1e9;
ll nivmax=0;
d[ind][roots[ind]]=0;
queue<int> coada;
coada.push(roots[ind]);
vector<int> edges;
while(!coada.empty())
{
int nod=coada.front();
nivmax=max(nivmax,d[ind][nod]);
coada.pop();
for(auto i:muchii[nod])
if(where[i.first]==ind&&d[ind][i.first]>d[ind][nod]+1)
{
d[ind][i.first]=d[ind][nod]+1;
inarb[i.second]=1;
edges.push_back(i.second);
coada.push(i.first);
}
}
//sort(edges.begin(),edges.end(),byniv);
for(int i=0;i<m;i++)
w[i]=1;
for(int j:edges)
w[j]=0;
/*ll val=ask(w);
if(val==dist*BB)
return roots[ind];*/
ll st=0;
ll dr=edges.size();
dr--;
ll ans=-1;
int poz=0;
while(st<=dr)
{
ll mij=(st+dr)/2;
for(int i=0;i<m;i++)
{
ll a=g[i].first,b=g[i].second;
if(a==roots[1]&&b==roots[2])
{
w[i]=0;
continue;
}
if(a==roots[2]&&b==roots[1])
{
w[i]=0;
continue;
}
if(where[a]!=where[b])
{
w[i]=1;
continue;
}
if(where[a]!=ind)
{
w[i]=0;
continue;
}
if(!inarb[i])
{
w[i]=0;
continue;
}
w[i]=1;
}
for(int j=0;j<=mij;j++)
w[edges[j]]=0;
ll x=ask(w);
int p=edges[mij];
int a=g[p].first;
int b=g[p].second;
if(x!=dist*AA)
st=mij+1;
else
{
poz=mij;
if(d[ind][a]<d[ind][b])
swap(a,b);
ans=a;
dr=mij-1;
}
}
if(ans==-1)
return roots[ind];
return ans;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
AA=A;
BB=B;
n=N;
m=U.size();
for(int i=0;i<m;i++)
{
int a=U[i],b=V[i];
g.push_back({a,b});
muchii[a].push_back({b,i});
muchii[b].push_back({a,i});
}
w.resize(m);
dist=ask(w)/A;
ll st=0;
ll dr=m-1;
while(st<=dr)
{
ll mij=(st+dr)/2;
for(int i=0;i<m;i++)
{
if(i<=mij)
w[i]=1;
else
w[i]=0;
}
ll val=ask(w);
if(val>dist*A)
{
roots[1]=g[mij].first;
roots[2]=g[mij].second;
dr=mij-1;
}
else
st=mij+1;
}
bfs(1);
bfs(2);
for(int i=0;i<n;i++)
{
if(d[1][i]<d[2][i])
where[i]=1;
if(d[2][i]<d[1][i])
where[i]=2;
}
int S=plsfind(1);
int T=plsfind(2);
answer(S,T);
}
Compilation message
highway.cpp: In function 'int plsfind(int)':
highway.cpp:116:9: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
116 | int poz=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6612 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6672 KB |
Output is correct |
| 2 |
Correct |
13 ms |
7388 KB |
Output is correct |
| 3 |
Correct |
106 ms |
13872 KB |
Output is correct |
| 4 |
Correct |
124 ms |
13548 KB |
Output is correct |
| 5 |
Correct |
96 ms |
13928 KB |
Output is correct |
| 6 |
Correct |
85 ms |
13676 KB |
Output is correct |
| 7 |
Correct |
91 ms |
13868 KB |
Output is correct |
| 8 |
Correct |
93 ms |
13612 KB |
Output is correct |
| 9 |
Correct |
117 ms |
13612 KB |
Output is correct |
| 10 |
Correct |
95 ms |
13632 KB |
Output is correct |
| 11 |
Correct |
148 ms |
13112 KB |
Output is correct |
| 12 |
Correct |
137 ms |
13456 KB |
Output is correct |
| 13 |
Correct |
89 ms |
13040 KB |
Output is correct |
| 14 |
Correct |
80 ms |
13032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
7388 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6676 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
7396 KB |
Output is correct |
| 2 |
Correct |
19 ms |
7460 KB |
Output is correct |
| 3 |
Correct |
120 ms |
14260 KB |
Output is correct |
| 4 |
Correct |
125 ms |
14664 KB |
Output is correct |
| 5 |
Correct |
213 ms |
16112 KB |
Output is correct |
| 6 |
Correct |
148 ms |
15932 KB |
Output is correct |
| 7 |
Correct |
168 ms |
16220 KB |
Output is correct |
| 8 |
Incorrect |
161 ms |
15432 KB |
Output is incorrect: {s, t} is wrong. |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
7312 KB |
Output is correct |
| 2 |
Correct |
13 ms |
7476 KB |
Output is correct |
| 3 |
Correct |
137 ms |
13836 KB |
Output is correct |
| 4 |
Correct |
137 ms |
14632 KB |
Output is correct |
| 5 |
Correct |
122 ms |
14664 KB |
Output is correct |
| 6 |
Incorrect |
152 ms |
15692 KB |
Output is incorrect: {s, t} is wrong. |
| 7 |
Halted |
0 ms |
0 KB |
- |
