#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[90000];
int dist1[90000], dist2[90000];
bool chk[90000];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
int M=U.size(), S, T, s, e, E;
vector<int> W(M,0), C1, C2;
queue<int> Q;
long long D=ask(W);
for(int i=0;i<M;i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
s=0; e=N-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<M;i++) W[i]=i<=m;
if(ask(W)!=D) e=m-1;
else s=m+1;
}
E=s;
memset(dist1,0x7f,sizeof(dist1));
memset(dist2,0x7f,sizeof(dist2));
dist1[U[E]]=0; Q.push(U[E]);
while(!Q.empty()) {
int c=Q.front();
Q.pop();
for(auto n: adj[c]) if(dist1[n]>dist1[c]+1) {
dist1[n]=dist1[c]+1;
Q.push(n);
}
}
dist2[V[E]]=0; Q.push(V[E]);
while(!Q.empty()) {
int c=Q.front();
Q.pop();
for(auto n: adj[c]) if(dist2[n]>dist2[c]+1) {
dist2[n]=dist2[c]+1;
Q.push(n);
}
}
for(int i=0;i<N;i++) {
if(dist1[i]<=dist2[i]) C1.push_back(i);
else if(dist1[i]>=dist2[i]) C2.push_back(i);
}
sort(C1.begin(),C1.end(),[&](int a, int b) {return dist1[a]<dist1[b];});
sort(C2.begin(),C2.end(),[&](int a, int b) {return dist2[a]<dist2[b];});
s=0; e=C1.size()-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<N;i++) chk[i]=false;
for(int i=m;i<C1.size();i++) chk[C1[i]]=true;
for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
if(ask(W)!=D) s=m+1;
else e=m-1;
}
S=C1[e];
s=0; e=C2.size()-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<N;i++) chk[i]=false;
for(int i=m;i<C2.size();i++) chk[C2[i]]=true;
for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
if(ask(W)!=D) s=m+1;
else e=m-1;
}
T=C2[e];
answer(S,T);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=m;i<C1.size();i++) chk[C1[i]]=true;
~^~~~~~~~~~
highway.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=m;i<C2.size();i++) chk[C2[i]]=true;
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3064 KB |
Output is correct |
2 |
Correct |
4 ms |
3064 KB |
Output is correct |
3 |
Correct |
4 ms |
3064 KB |
Output is correct |
4 |
Correct |
4 ms |
3064 KB |
Output is correct |
5 |
Correct |
4 ms |
3084 KB |
Output is correct |
6 |
Correct |
4 ms |
3064 KB |
Output is correct |
7 |
Correct |
4 ms |
3076 KB |
Output is correct |
8 |
Correct |
4 ms |
3064 KB |
Output is correct |
9 |
Correct |
4 ms |
3080 KB |
Output is correct |
10 |
Correct |
4 ms |
3064 KB |
Output is correct |
11 |
Correct |
4 ms |
3164 KB |
Output is correct |
12 |
Correct |
4 ms |
3112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3192 KB |
Output is correct |
2 |
Correct |
25 ms |
3836 KB |
Output is correct |
3 |
Correct |
211 ms |
8432 KB |
Output is correct |
4 |
Correct |
194 ms |
8436 KB |
Output is correct |
5 |
Correct |
203 ms |
8556 KB |
Output is correct |
6 |
Correct |
205 ms |
8476 KB |
Output is correct |
7 |
Correct |
215 ms |
8412 KB |
Output is correct |
8 |
Correct |
199 ms |
8420 KB |
Output is correct |
9 |
Correct |
207 ms |
8420 KB |
Output is correct |
10 |
Correct |
207 ms |
8672 KB |
Output is correct |
11 |
Correct |
217 ms |
8376 KB |
Output is correct |
12 |
Correct |
212 ms |
8380 KB |
Output is correct |
13 |
Correct |
215 ms |
8292 KB |
Output is correct |
14 |
Correct |
201 ms |
8308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3716 KB |
Output is correct |
2 |
Correct |
43 ms |
4324 KB |
Output is correct |
3 |
Correct |
67 ms |
4864 KB |
Output is correct |
4 |
Correct |
176 ms |
8256 KB |
Output is correct |
5 |
Correct |
167 ms |
8184 KB |
Output is correct |
6 |
Correct |
175 ms |
8432 KB |
Output is correct |
7 |
Correct |
183 ms |
8292 KB |
Output is correct |
8 |
Correct |
187 ms |
8188 KB |
Output is correct |
9 |
Correct |
180 ms |
8280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3096 KB |
Output is correct |
2 |
Correct |
20 ms |
3664 KB |
Output is correct |
3 |
Correct |
171 ms |
7452 KB |
Output is correct |
4 |
Correct |
207 ms |
8408 KB |
Output is correct |
5 |
Correct |
199 ms |
8456 KB |
Output is correct |
6 |
Correct |
203 ms |
8376 KB |
Output is correct |
7 |
Correct |
201 ms |
8424 KB |
Output is correct |
8 |
Correct |
207 ms |
8368 KB |
Output is correct |
9 |
Correct |
212 ms |
8552 KB |
Output is correct |
10 |
Correct |
212 ms |
8420 KB |
Output is correct |
11 |
Correct |
207 ms |
8500 KB |
Output is correct |
12 |
Correct |
213 ms |
8372 KB |
Output is correct |
13 |
Correct |
204 ms |
8432 KB |
Output is correct |
14 |
Correct |
211 ms |
8304 KB |
Output is correct |
15 |
Correct |
203 ms |
8448 KB |
Output is correct |
16 |
Correct |
200 ms |
8396 KB |
Output is correct |
17 |
Correct |
215 ms |
8300 KB |
Output is correct |
18 |
Correct |
220 ms |
8300 KB |
Output is correct |
19 |
Correct |
199 ms |
8456 KB |
Output is correct |
20 |
Correct |
216 ms |
8292 KB |
Output is correct |
21 |
Correct |
190 ms |
9172 KB |
Output is correct |
22 |
Correct |
187 ms |
9176 KB |
Output is correct |
23 |
Correct |
192 ms |
8972 KB |
Output is correct |
24 |
Correct |
214 ms |
8804 KB |
Output is correct |
25 |
Correct |
214 ms |
8460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
3832 KB |
Output is correct |
2 |
Correct |
30 ms |
3752 KB |
Output is correct |
3 |
Correct |
225 ms |
8648 KB |
Output is correct |
4 |
Correct |
261 ms |
9036 KB |
Output is correct |
5 |
Correct |
304 ms |
9600 KB |
Output is correct |
6 |
Correct |
297 ms |
9460 KB |
Output is correct |
7 |
Correct |
290 ms |
9496 KB |
Output is correct |
8 |
Correct |
311 ms |
9464 KB |
Output is correct |
9 |
Incorrect |
254 ms |
7672 KB |
Output is incorrect: {s, t} is wrong. |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3668 KB |
Output is correct |
2 |
Correct |
29 ms |
3824 KB |
Output is correct |
3 |
Correct |
230 ms |
8824 KB |
Output is correct |
4 |
Correct |
275 ms |
8828 KB |
Output is correct |
5 |
Correct |
260 ms |
8912 KB |
Output is correct |
6 |
Correct |
282 ms |
9340 KB |
Output is correct |
7 |
Correct |
217 ms |
8776 KB |
Output is correct |
8 |
Correct |
263 ms |
8784 KB |
Output is correct |
9 |
Correct |
257 ms |
9048 KB |
Output is correct |
10 |
Correct |
285 ms |
9496 KB |
Output is correct |
11 |
Correct |
299 ms |
9488 KB |
Output is correct |
12 |
Correct |
307 ms |
9516 KB |
Output is correct |
13 |
Incorrect |
252 ms |
8064 KB |
Output is incorrect: {s, t} is wrong. |
14 |
Halted |
0 ms |
0 KB |
- |