#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int MN = 9e4+4, MM = 1.3e5+5;
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 = 1, 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+1;i<ls.size();i++) q[ls[i]]=1;
bool heh = (ask(q)==st);
if(heh) hi=mmm;
else lo=mmm+1;
}
if(lo==ls.size()){
if(ls.empty()){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;
}
}
else{
x = U[ls[lo]], y = V[ls[lo]];
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+1;i<ls.size();i++) q[ls[i]]=1;
bool heh = (ask(q)==st);
if(heh) hi=mmm;
else lo=mmm+1;
}
if(lo==ls.size()){
if(ls.empty()){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;
}
}
else{
x = U[ls[lo]], y = V[ls[lo]];
if(d[x]>d[y]) t = x;
else t = y;
}
answer(s, t);
}
Compilation message
highway.cpp: In function 'void sett(ll)':
highway.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();i++)
~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:32:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
ll m = lo+hi>>1;
~~^~~
highway.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
ll mmm = lo+hi>>1;
~~^~~
highway.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
~^~~~~~~~~~
highway.cpp:64:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lo==ls.size()){
~~^~~~~~~~~~~
highway.cpp:82:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
ll mmm = lo+hi>>1;
~~^~~
highway.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=mmm+1;i<ls.size();i++) q[ls[i]]=1;
~^~~~~~~~~~
highway.cpp:89:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lo==ls.size()){
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4652 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4856 KB |
Output is correct |
| 2 |
Correct |
44 ms |
6952 KB |
Output is correct |
| 3 |
Correct |
489 ms |
25452 KB |
Output is correct |
| 4 |
Correct |
535 ms |
25460 KB |
Output is correct |
| 5 |
Correct |
561 ms |
25868 KB |
Output is correct |
| 6 |
Correct |
469 ms |
24676 KB |
Output is correct |
| 7 |
Correct |
466 ms |
24412 KB |
Output is correct |
| 8 |
Correct |
570 ms |
25936 KB |
Output is correct |
| 9 |
Correct |
445 ms |
24552 KB |
Output is correct |
| 10 |
Correct |
510 ms |
25032 KB |
Output is correct |
| 11 |
Correct |
375 ms |
23740 KB |
Output is correct |
| 12 |
Correct |
556 ms |
27992 KB |
Output is correct |
| 13 |
Correct |
547 ms |
28520 KB |
Output is correct |
| 14 |
Incorrect |
597 ms |
28364 KB |
Output is incorrect: {s, t} is wrong. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
7824 KB |
Output is correct |
| 2 |
Correct |
63 ms |
10792 KB |
Output is correct |
| 3 |
Correct |
93 ms |
10460 KB |
Output is correct |
| 4 |
Correct |
278 ms |
29284 KB |
Output is correct |
| 5 |
Correct |
274 ms |
29484 KB |
Output is correct |
| 6 |
Correct |
284 ms |
31856 KB |
Output is correct |
| 7 |
Correct |
233 ms |
21236 KB |
Output is correct |
| 8 |
Correct |
274 ms |
30500 KB |
Output is correct |
| 9 |
Correct |
239 ms |
24324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4816 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
7092 KB |
Output is correct |
| 2 |
Correct |
59 ms |
7248 KB |
Output is correct |
| 3 |
Correct |
631 ms |
27508 KB |
Output is correct |
| 4 |
Correct |
736 ms |
28436 KB |
Output is correct |
| 5 |
Correct |
750 ms |
31528 KB |
Output is correct |
| 6 |
Correct |
768 ms |
31972 KB |
Output is correct |
| 7 |
Correct |
790 ms |
31708 KB |
Output is correct |
| 8 |
Correct |
731 ms |
31948 KB |
Output is correct |
| 9 |
Incorrect |
526 ms |
27140 KB |
Output is incorrect: {s, t} is wrong. |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
7160 KB |
Output is correct |
| 2 |
Correct |
57 ms |
7288 KB |
Output is correct |
| 3 |
Correct |
629 ms |
27220 KB |
Output is correct |
| 4 |
Correct |
633 ms |
27768 KB |
Output is correct |
| 5 |
Correct |
640 ms |
28560 KB |
Output is correct |
| 6 |
Incorrect |
741 ms |
32208 KB |
Output is incorrect: {s, t} is wrong. |
| 7 |
Halted |
0 ms |
0 KB |
- |
