#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);
}
}
s=0; e=D/A-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<M;i++) W[i]=(dist1[U[i]]<dist2[U[i]] && dist1[U[i]]>=m)^(dist1[V[i]]<dist2[V[i]] && dist1[V[i]]>=m);
if(ask(W)!=D) s=m+1;
else e=m-1;
}
while(0>e && e>=D/A);
for(int i=0;i<N;i++) {
if(dist1[i]<dist2[i] && dist1[i]==e) C1.push_back(i);
if(dist1[i]>dist2[i] && dist2[i]==D/A-s) C2.push_back(i);
chk[i]=false;
}
//while(C1.empty() || C2.empty());
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=0;i<=m;i++) chk[C1[i]]=true;
for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
if(ask(W)!=D) e=m-1;
else s=m+1;
}
//while(0>s && s>=C1.size());
S=C1[s];
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=0;i<=m;i++) chk[C2[i]]=true;
for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
if(ask(W)!=D) e=m-1;
else s=m+1;
}
//while(0>s && s>=C2.size());
T=C2[s];
answer(S,T);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:55:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
while(0>e && e>=D/A);
^~~~~
highway.cpp:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
for(int i=0;i<N;i++) {
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3076 KB |
Output is correct |
2 |
Correct |
4 ms |
3112 KB |
Output is correct |
3 |
Correct |
4 ms |
3084 KB |
Output is correct |
4 |
Correct |
4 ms |
3064 KB |
Output is correct |
5 |
Correct |
5 ms |
3064 KB |
Output is correct |
6 |
Correct |
4 ms |
3084 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 |
3192 KB |
Output is correct |
10 |
Correct |
4 ms |
3084 KB |
Output is correct |
11 |
Correct |
4 ms |
3064 KB |
Output is correct |
12 |
Correct |
4 ms |
3064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3192 KB |
Output is correct |
2 |
Correct |
25 ms |
3576 KB |
Output is correct |
3 |
Correct |
201 ms |
8048 KB |
Output is correct |
4 |
Correct |
210 ms |
8048 KB |
Output is correct |
5 |
Correct |
205 ms |
8064 KB |
Output is correct |
6 |
Correct |
204 ms |
8072 KB |
Output is correct |
7 |
Correct |
185 ms |
8016 KB |
Output is correct |
8 |
Correct |
199 ms |
8004 KB |
Output is correct |
9 |
Correct |
198 ms |
7960 KB |
Output is correct |
10 |
Correct |
204 ms |
8128 KB |
Output is correct |
11 |
Correct |
193 ms |
7744 KB |
Output is correct |
12 |
Correct |
215 ms |
7736 KB |
Output is correct |
13 |
Correct |
211 ms |
7908 KB |
Output is correct |
14 |
Correct |
195 ms |
7732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
3580 KB |
Output is correct |
2 |
Correct |
41 ms |
4088 KB |
Output is correct |
3 |
Correct |
58 ms |
4704 KB |
Output is correct |
4 |
Correct |
190 ms |
7784 KB |
Output is correct |
5 |
Correct |
116 ms |
7760 KB |
Output is correct |
6 |
Correct |
175 ms |
7812 KB |
Output is correct |
7 |
Correct |
152 ms |
7736 KB |
Output is correct |
8 |
Correct |
169 ms |
7720 KB |
Output is correct |
9 |
Correct |
153 ms |
7732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3192 KB |
Output is correct |
2 |
Correct |
21 ms |
3664 KB |
Output is correct |
3 |
Correct |
142 ms |
6996 KB |
Output is correct |
4 |
Correct |
210 ms |
8084 KB |
Output is correct |
5 |
Correct |
186 ms |
7936 KB |
Output is correct |
6 |
Correct |
193 ms |
7912 KB |
Output is correct |
7 |
Correct |
193 ms |
7992 KB |
Output is correct |
8 |
Correct |
186 ms |
7988 KB |
Output is correct |
9 |
Correct |
211 ms |
8032 KB |
Output is correct |
10 |
Correct |
200 ms |
8056 KB |
Output is correct |
11 |
Correct |
198 ms |
7816 KB |
Output is correct |
12 |
Correct |
211 ms |
7912 KB |
Output is correct |
13 |
Correct |
209 ms |
7756 KB |
Output is correct |
14 |
Correct |
215 ms |
7804 KB |
Output is correct |
15 |
Correct |
189 ms |
7996 KB |
Output is correct |
16 |
Correct |
187 ms |
7908 KB |
Output is correct |
17 |
Correct |
231 ms |
7740 KB |
Output is correct |
18 |
Correct |
234 ms |
7820 KB |
Output is correct |
19 |
Correct |
198 ms |
7952 KB |
Output is correct |
20 |
Correct |
214 ms |
7796 KB |
Output is correct |
21 |
Correct |
180 ms |
9168 KB |
Output is correct |
22 |
Correct |
209 ms |
9224 KB |
Output is correct |
23 |
Correct |
205 ms |
8980 KB |
Output is correct |
24 |
Correct |
222 ms |
8880 KB |
Output is correct |
25 |
Correct |
228 ms |
7964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3748 KB |
Output is correct |
2 |
Correct |
31 ms |
3728 KB |
Output is correct |
3 |
Correct |
258 ms |
8504 KB |
Output is correct |
4 |
Correct |
257 ms |
8524 KB |
Output is correct |
5 |
Correct |
295 ms |
9012 KB |
Output is correct |
6 |
Correct |
280 ms |
9036 KB |
Output is correct |
7 |
Correct |
289 ms |
8980 KB |
Output is correct |
8 |
Correct |
278 ms |
8992 KB |
Output is correct |
9 |
Runtime error |
248 ms |
14792 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3704 KB |
Output is correct |
2 |
Correct |
29 ms |
3644 KB |
Output is correct |
3 |
Correct |
224 ms |
8272 KB |
Output is correct |
4 |
Correct |
226 ms |
8348 KB |
Output is correct |
5 |
Correct |
248 ms |
8472 KB |
Output is correct |
6 |
Correct |
296 ms |
9164 KB |
Output is correct |
7 |
Correct |
225 ms |
8304 KB |
Output is correct |
8 |
Correct |
238 ms |
8352 KB |
Output is correct |
9 |
Correct |
235 ms |
8468 KB |
Output is correct |
10 |
Correct |
280 ms |
8960 KB |
Output is correct |
11 |
Correct |
286 ms |
9092 KB |
Output is correct |
12 |
Correct |
273 ms |
9120 KB |
Output is correct |
13 |
Runtime error |
245 ms |
15556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
14 |
Halted |
0 ms |
0 KB |
- |