#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];
vector<int> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
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(int i:muchii[nod])
if(d[ind][i]>d[ind][nod]+1)
{
d[ind][i]=d[ind][nod]+1;
coada.push(i);
}
}
}
bool good[100005],mark[100005];
ll firstsearch(ll ind,ll nivmax)
{
for(int i=0;i<m;i++)
{
ll a=g[i].first;
ll b=g[i].second;
if(d[ind][a]<d[ind][b])
swap(a,b);
if(good[a]&&d[ind][a]<=nivmax&&d[ind][a]==d[ind][b]+1)
w[i]=0;
else
w[i]=1;
}
return ask(w);
}
ll secondsearch(ll ind)
{
for(int i=0;i<m;i++)
{
ll a=g[i].first;
ll b=g[i].second;
if(d[ind][a]<d[ind][b])
swap(a,b);
if(mark[a]&&d[ind][a]==d[ind][b]+1)
w[i]=0;
else
w[i]=1;
}
return ask(w);
}
int plsfind(int ind)
{
int u=roots[ind];
ll nivmax=0;
for(int i=0;i<n;i++)
{
good[i]=0;
if(d[ind][i]<d[3-ind][i])
{
nivmax=max(nivmax,d[ind][i]);
good[i]=1;
}
}
int myniv=0;
int st=0;
int dr=nivmax;
while(st<=dr)
{
int mij=(st+dr)/2;
ll val=firstsearch(ind,mij);
if(mij<=dist&&val==(dist-mij)*BB+mij*AA)
{
myniv=mij;
st=mij+1;
}
else
dr=mij-1;
}
vector<int> cand;
for(int i=0;i<n;i++)
if(good[i]&&d[ind][i]==myniv)
cand.push_back(i);
while(true)
{
if(cand.size()==1)
return cand[0];
vector<int> x;
vector<int> y;
int lg=cand.size();
for(int i=0;i<cand.size();i++)
{
if(i<lg/2)
x.push_back(cand[i]);
else
y.push_back(cand[i]);
}
for(int i=0;i<n;i++)
mark[i]=0;
for(int i:x)
mark[i]=1;
ll val=secondsearch(ind);
if(val<dist*BB)
cand=x;
else
cand=y;
}
}
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);
muchii[b].push_back(a);
}
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);
int S=plsfind(1);
int T=plsfind(2);
answer(S,T);
}
Compilation message
highway.cpp: In function 'int plsfind(int)':
highway.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i=0;i<cand.size();i++)
| ~^~~~~~~~~~~~
highway.cpp:66:9: warning: unused variable 'u' [-Wunused-variable]
66 | int u=roots[ind];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4564 KB |
Output is correct |
2 |
Correct |
1 ms |
4564 KB |
Output is correct |
3 |
Correct |
1 ms |
4568 KB |
Output is correct |
4 |
Correct |
1 ms |
4564 KB |
Output is correct |
5 |
Correct |
1 ms |
4560 KB |
Output is correct |
6 |
Correct |
1 ms |
4560 KB |
Output is correct |
7 |
Correct |
1 ms |
4564 KB |
Output is correct |
8 |
Correct |
1 ms |
4560 KB |
Output is correct |
9 |
Correct |
1 ms |
4564 KB |
Output is correct |
10 |
Correct |
1 ms |
4564 KB |
Output is correct |
11 |
Correct |
1 ms |
4560 KB |
Output is correct |
12 |
Correct |
1 ms |
4564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4616 KB |
Output is correct |
2 |
Correct |
11 ms |
5364 KB |
Output is correct |
3 |
Correct |
106 ms |
11976 KB |
Output is correct |
4 |
Correct |
111 ms |
12092 KB |
Output is correct |
5 |
Correct |
100 ms |
11976 KB |
Output is correct |
6 |
Correct |
89 ms |
11640 KB |
Output is correct |
7 |
Correct |
88 ms |
11980 KB |
Output is correct |
8 |
Correct |
101 ms |
11632 KB |
Output is correct |
9 |
Correct |
89 ms |
11624 KB |
Output is correct |
10 |
Correct |
96 ms |
11972 KB |
Output is correct |
11 |
Correct |
160 ms |
12096 KB |
Output is correct |
12 |
Correct |
139 ms |
11600 KB |
Output is correct |
13 |
Correct |
117 ms |
12088 KB |
Output is correct |
14 |
Correct |
129 ms |
12180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5256 KB |
Output is correct |
2 |
Correct |
26 ms |
5924 KB |
Output is correct |
3 |
Correct |
42 ms |
6660 KB |
Output is correct |
4 |
Correct |
73 ms |
11152 KB |
Output is correct |
5 |
Correct |
76 ms |
11400 KB |
Output is correct |
6 |
Correct |
110 ms |
11152 KB |
Output is correct |
7 |
Correct |
128 ms |
11156 KB |
Output is correct |
8 |
Correct |
91 ms |
11392 KB |
Output is correct |
9 |
Correct |
108 ms |
11368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4616 KB |
Output is correct |
2 |
Correct |
16 ms |
5292 KB |
Output is correct |
3 |
Correct |
69 ms |
10100 KB |
Output is correct |
4 |
Correct |
100 ms |
11664 KB |
Output is correct |
5 |
Correct |
94 ms |
11616 KB |
Output is correct |
6 |
Correct |
82 ms |
11608 KB |
Output is correct |
7 |
Correct |
115 ms |
11628 KB |
Output is correct |
8 |
Correct |
88 ms |
11616 KB |
Output is correct |
9 |
Correct |
109 ms |
11956 KB |
Output is correct |
10 |
Correct |
106 ms |
11972 KB |
Output is correct |
11 |
Correct |
116 ms |
11624 KB |
Output is correct |
12 |
Correct |
122 ms |
11624 KB |
Output is correct |
13 |
Correct |
150 ms |
11708 KB |
Output is correct |
14 |
Correct |
126 ms |
11408 KB |
Output is correct |
15 |
Correct |
96 ms |
11544 KB |
Output is correct |
16 |
Correct |
128 ms |
11760 KB |
Output is correct |
17 |
Correct |
114 ms |
11476 KB |
Output is correct |
18 |
Correct |
117 ms |
12100 KB |
Output is correct |
19 |
Correct |
82 ms |
11864 KB |
Output is correct |
20 |
Correct |
105 ms |
11492 KB |
Output is correct |
21 |
Correct |
82 ms |
12884 KB |
Output is correct |
22 |
Correct |
109 ms |
12888 KB |
Output is correct |
23 |
Incorrect |
132 ms |
13124 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
5388 KB |
Output is correct |
2 |
Incorrect |
16 ms |
5336 KB |
Output is incorrect: {s, t} is wrong. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
13 ms |
5308 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |