#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=100005;
const int mmax=130005;
int n,m,i,p,u,ret;
long long mx,cate,A,B;
int unu[mmax],doi[mmax];
bool always[mmax];
bool inA[nmax],inB[nmax];
int in[nmax],bun[nmax];
int qu[2][nmax],d[2][nmax];
vector<int> v[nmax];
vector<int> q;
long long dist(int x)
{
for(i=0;i<m;i++)
q[i]=1;
for(i=0;i<x;i++)
q[i]=0;
return ask(q);
}
void bfs(int x,int wh)
{
int nod;
u=1;
qu[wh][u]=x;d[wh][x]=1;
for(p=1;p<=u;p++)
{
x=qu[wh][p];
for(i=0;i<v[x].size();i++)
{
nod=v[x][i];
if(!d[wh][nod])
{
d[wh][nod]=d[wh][x]+1;
qu[wh][++u]=nod;
}
}
}
}
int cb(vector<int> mult)
{
int ans=0;
for(i=0;i<n;i++)
in[i]=0;
for(i=0;i<mult.size();i++)
in[mult[i]]=1;
for(int p=17;p>=0;p--)
if(ans+(1<<p)<=mult.size())
{
ans+=(1<<p);
for(i=0;i<m;i++)
if(always[i]) q[i]=0;
else q[i]=1;
q[ret]=0;
for(i=0;i<n;i++)
bun[i]=0;
for(i=0;i<ans;i++)
bun[mult[i]]=1;
for(i=0;i<m;i++)
if(bun[unu[i]]&&bun[doi[i]])
q[i]=0;
long long cat=ask(q);
if(cat==1LL*cate*A) ans-=(1<<p);
}
return mult[ans];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int Aa, int Bb) {
n=N;m = U.size();
q.resize(m);
A=Aa;B=Bb;
for(i=0;i<m;i++)
{
v[U[i]].push_back(V[i]);
v[V[i]].push_back(U[i]);
unu[i]=U[i];doi[i]=V[i];
}
for(i=0;i<m;i++)
q[i]=1;
mx=ask(q);
cate=mx/B;
for(int p=17;p>=0;p--)
if(ret+(1<<p)<=m&&dist(ret+(1<<p))==mx)
ret+=(1<<p);
int a=U[ret],b=V[ret];
bfs(a,0);bfs(b,1);
vector<int> multA,multB;
for(i=1;i<=n;i++)
{
int nod=qu[0][i];
if(d[0][nod]<d[1][nod])
{
multA.push_back(nod);
inA[nod]=1;
}
nod=qu[1][i];
if(d[1][nod]<d[0][nod])
{
multB.push_back(nod);
inB[nod]=1;
}
}
for(i=0;i<m;i++)
if(inB[U[i]]&&inB[V[i]])
always[i]=1;
int x=cb(multA);
for(i=0;i<m;i++)
always[i]=0;
for(i=0;i<m;i++)
if(inA[U[i]]&&inA[V[i]])
always[i]=1;
int y=cb(multB);
answer(x,y);
}
Compilation message
highway.cpp: In function 'void bfs(int, int)':
highway.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
highway.cpp: In function 'int cb(std::vector<int>)':
highway.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<mult.size();i++)
~^~~~~~~~~~~~
highway.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans+(1<<p)<=mult.size())
~~~~~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2680 KB |
Output is correct |
11 |
Correct |
4 ms |
2680 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2808 KB |
Output is correct |
2 |
Correct |
29 ms |
3576 KB |
Output is correct |
3 |
Correct |
276 ms |
11284 KB |
Output is correct |
4 |
Correct |
272 ms |
11332 KB |
Output is correct |
5 |
Correct |
277 ms |
11544 KB |
Output is correct |
6 |
Correct |
248 ms |
11312 KB |
Output is correct |
7 |
Correct |
255 ms |
11380 KB |
Output is correct |
8 |
Correct |
230 ms |
11512 KB |
Output is correct |
9 |
Correct |
226 ms |
11252 KB |
Output is correct |
10 |
Correct |
270 ms |
11464 KB |
Output is correct |
11 |
Correct |
266 ms |
11196 KB |
Output is correct |
12 |
Correct |
270 ms |
11228 KB |
Output is correct |
13 |
Correct |
257 ms |
11276 KB |
Output is correct |
14 |
Correct |
277 ms |
11268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3640 KB |
Output is correct |
2 |
Correct |
49 ms |
4592 KB |
Output is correct |
3 |
Correct |
70 ms |
5560 KB |
Output is correct |
4 |
Correct |
179 ms |
10900 KB |
Output is correct |
5 |
Correct |
211 ms |
10900 KB |
Output is correct |
6 |
Correct |
206 ms |
11316 KB |
Output is correct |
7 |
Correct |
206 ms |
11064 KB |
Output is correct |
8 |
Correct |
208 ms |
11164 KB |
Output is correct |
9 |
Correct |
213 ms |
11056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
30 ms |
3576 KB |
Output is correct |
3 |
Correct |
177 ms |
9544 KB |
Output is correct |
4 |
Correct |
244 ms |
11280 KB |
Output is correct |
5 |
Correct |
232 ms |
11320 KB |
Output is correct |
6 |
Correct |
225 ms |
11292 KB |
Output is correct |
7 |
Correct |
221 ms |
11200 KB |
Output is correct |
8 |
Correct |
234 ms |
11156 KB |
Output is correct |
9 |
Correct |
354 ms |
11316 KB |
Output is correct |
10 |
Correct |
258 ms |
11320 KB |
Output is correct |
11 |
Correct |
269 ms |
11224 KB |
Output is correct |
12 |
Correct |
290 ms |
11304 KB |
Output is correct |
13 |
Correct |
258 ms |
11296 KB |
Output is correct |
14 |
Correct |
259 ms |
11224 KB |
Output is correct |
15 |
Correct |
230 ms |
11308 KB |
Output is correct |
16 |
Correct |
232 ms |
11312 KB |
Output is correct |
17 |
Correct |
251 ms |
11580 KB |
Output is correct |
18 |
Correct |
250 ms |
11304 KB |
Output is correct |
19 |
Correct |
234 ms |
11400 KB |
Output is correct |
20 |
Correct |
296 ms |
11280 KB |
Output is correct |
21 |
Correct |
233 ms |
11600 KB |
Output is correct |
22 |
Correct |
217 ms |
11476 KB |
Output is correct |
23 |
Correct |
257 ms |
11456 KB |
Output is correct |
24 |
Correct |
254 ms |
11444 KB |
Output is correct |
25 |
Correct |
265 ms |
11380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
3752 KB |
Output is correct |
2 |
Correct |
34 ms |
3704 KB |
Output is correct |
3 |
Correct |
294 ms |
11616 KB |
Output is correct |
4 |
Correct |
334 ms |
12048 KB |
Output is correct |
5 |
Correct |
365 ms |
12412 KB |
Output is correct |
6 |
Correct |
355 ms |
12408 KB |
Output is correct |
7 |
Correct |
333 ms |
12428 KB |
Output is correct |
8 |
Correct |
371 ms |
12524 KB |
Output is correct |
9 |
Correct |
285 ms |
9080 KB |
Output is correct |
10 |
Correct |
285 ms |
9356 KB |
Output is correct |
11 |
Correct |
317 ms |
9800 KB |
Output is correct |
12 |
Correct |
346 ms |
11436 KB |
Output is correct |
13 |
Correct |
373 ms |
12016 KB |
Output is correct |
14 |
Correct |
391 ms |
12340 KB |
Output is correct |
15 |
Correct |
329 ms |
12316 KB |
Output is correct |
16 |
Correct |
317 ms |
10080 KB |
Output is correct |
17 |
Correct |
240 ms |
11788 KB |
Output is correct |
18 |
Correct |
246 ms |
12060 KB |
Output is correct |
19 |
Correct |
254 ms |
11704 KB |
Output is correct |
20 |
Correct |
257 ms |
11780 KB |
Output is correct |
21 |
Correct |
340 ms |
12576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
3736 KB |
Output is correct |
2 |
Correct |
32 ms |
3704 KB |
Output is correct |
3 |
Correct |
303 ms |
11464 KB |
Output is correct |
4 |
Correct |
276 ms |
11920 KB |
Output is correct |
5 |
Correct |
295 ms |
11788 KB |
Output is correct |
6 |
Incorrect |
306 ms |
12560 KB |
Output is incorrect: {s, t} is wrong |
7 |
Halted |
0 ms |
0 KB |
- |