#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int MN = 150005;
ll m, st, lo, hi, mm, i, x, y, vis[MN], s, t, d[MN], u[MN]; vector<int> q;
map<pair<ll,ll>,ll> id;
vector<ll> adj[MN], tr[MN], ls;
queue<ll> qq;
void sett(ll l){
for(int i=0;i<q.size();i++)
q[i]=(i<=l);
}
void dfs(ll n){
for(auto v : tr[n]){
ls.push_back(id[{v, n}]);
d[v] = d[n]+1; dfs(v);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
A = B = 0; m = U.size();
for(i=0;i<m;i++) q.push_back(0);
for(i=0;i<m;i++){
x = U[i], y = V[i];
id[{x,y}]=id[{y,x}]=i;
adj[x].push_back(y);
adj[y].push_back(x);
}
st = ask(q);
lo = 0, hi = m;
while(lo<hi){
ll m = lo+hi>>1;
sett(m);
bool heh = (ask(q)==st);
if(heh) lo=m+1;
else hi=m;
}
mm = lo-1; sett(mm);
x = U[mm+1], y = V[mm+1];
qq.push(x); qq.push(y); vis[x]=vis[y]=1;
while(qq.size()){
x = qq.front(); qq.pop();
for(auto v : adj[x]){
if(id[{x,v}]>mm&&!vis[v]){
vis[v] = 1;
qq.push(v);
tr[x].push_back(v);
u[id[{x,v}]]=1;
}
}
}
u[mm+1]=1;
x = U[mm+1], y = V[mm+1];
dfs(x);
lo = 0; hi = ls.size();
while(lo<hi){
ll mmm = lo+hi>>1;
for(i=0;i<m;i++) q[i]=!u[i];
for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
bool heh = (ask(q)==st);
if(heh) hi=mmm;
else lo=mmm+1;
}
if(lo==0){
s = U[mm+1];
}
else{
x = U[ls[lo-1]], y = V[ls[lo-1]];
if(d[x]>d[y]) s = x;
else s = y;
}
ls.clear();
x = U[mm+1], y = V[mm+1];
dfs(y);
lo = 0; hi = ls.size();
while(lo<hi){
ll mmm = lo+hi>>1;
for(i=0;i<m;i++) q[i]=!u[i];
for(i=mmm;i<ls.size();i++) q[ls[i]]=1;
bool heh = (ask(q)==st);
if(heh) hi=mmm;
else lo=mmm+1;
}
if(lo==0){
t = V[mm+1];
}
else{
x = U[ls[lo-1]], y = V[ls[lo-1]];
if(d[x]>d[y]) t = x;
else t = y;
}
answer(s, t);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7396 KB |
Output is correct |
2 |
Correct |
8 ms |
7392 KB |
Output is correct |
3 |
Correct |
8 ms |
7388 KB |
Output is correct |
4 |
Correct |
9 ms |
7288 KB |
Output is correct |
5 |
Correct |
8 ms |
7388 KB |
Output is correct |
6 |
Correct |
8 ms |
7288 KB |
Output is correct |
7 |
Correct |
8 ms |
7468 KB |
Output is correct |
8 |
Correct |
8 ms |
7288 KB |
Output is correct |
9 |
Correct |
8 ms |
7472 KB |
Output is correct |
10 |
Correct |
8 ms |
7388 KB |
Output is correct |
11 |
Correct |
9 ms |
7416 KB |
Output is correct |
12 |
Correct |
8 ms |
7328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7544 KB |
Output is correct |
2 |
Correct |
47 ms |
9852 KB |
Output is correct |
3 |
Correct |
532 ms |
28400 KB |
Output is correct |
4 |
Correct |
512 ms |
28256 KB |
Output is correct |
5 |
Correct |
569 ms |
28640 KB |
Output is correct |
6 |
Correct |
471 ms |
27548 KB |
Output is correct |
7 |
Correct |
448 ms |
27364 KB |
Output is correct |
8 |
Correct |
547 ms |
28888 KB |
Output is correct |
9 |
Correct |
452 ms |
27372 KB |
Output is correct |
10 |
Correct |
514 ms |
27752 KB |
Output is correct |
11 |
Correct |
382 ms |
26560 KB |
Output is correct |
12 |
Correct |
577 ms |
30824 KB |
Output is correct |
13 |
Correct |
559 ms |
31276 KB |
Output is correct |
14 |
Correct |
586 ms |
31452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
10648 KB |
Output is correct |
2 |
Correct |
65 ms |
13608 KB |
Output is correct |
3 |
Correct |
80 ms |
13288 KB |
Output is correct |
4 |
Correct |
277 ms |
32108 KB |
Output is correct |
5 |
Correct |
291 ms |
32248 KB |
Output is correct |
6 |
Correct |
278 ms |
34680 KB |
Output is correct |
7 |
Correct |
254 ms |
24068 KB |
Output is correct |
8 |
Correct |
295 ms |
33452 KB |
Output is correct |
9 |
Correct |
259 ms |
27148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7592 KB |
Output is correct |
2 |
Correct |
46 ms |
9592 KB |
Output is correct |
3 |
Correct |
394 ms |
24276 KB |
Output is correct |
4 |
Correct |
488 ms |
28248 KB |
Output is correct |
5 |
Correct |
318 ms |
25828 KB |
Output is correct |
6 |
Correct |
341 ms |
25704 KB |
Output is correct |
7 |
Correct |
451 ms |
27256 KB |
Output is correct |
8 |
Correct |
368 ms |
26076 KB |
Output is correct |
9 |
Correct |
519 ms |
28436 KB |
Output is correct |
10 |
Correct |
486 ms |
27628 KB |
Output is correct |
11 |
Correct |
547 ms |
30936 KB |
Output is correct |
12 |
Correct |
524 ms |
31168 KB |
Output is correct |
13 |
Correct |
491 ms |
30132 KB |
Output is correct |
14 |
Correct |
449 ms |
26968 KB |
Output is correct |
15 |
Correct |
348 ms |
25892 KB |
Output is correct |
16 |
Correct |
350 ms |
23976 KB |
Output is correct |
17 |
Correct |
538 ms |
30804 KB |
Output is correct |
18 |
Correct |
577 ms |
31836 KB |
Output is correct |
19 |
Correct |
436 ms |
24464 KB |
Output is correct |
20 |
Correct |
344 ms |
25704 KB |
Output is correct |
21 |
Correct |
438 ms |
27428 KB |
Output is correct |
22 |
Correct |
389 ms |
26436 KB |
Output is correct |
23 |
Correct |
519 ms |
27960 KB |
Output is correct |
24 |
Correct |
497 ms |
28532 KB |
Output is correct |
25 |
Correct |
581 ms |
36184 KB |
Output is correct |