#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
const int inf = 1e18+10;
const int maxn = 9e4+10;
int n, m, par[maxn], parid[maxn];
vector<int> g[maxn];
void find_pair(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A, int32_t B) {
// int M = U.size();
// for (int j = 0; j < 50; ++j) {
// std::vector<int> w(M);
// for (int i = 0; i < M; ++i) {
// w[i] = 0;
// }
// long long toll = ask(w);
// }
// answer(0, N - 1);
n = N;
m = U.size();
for(int i = 0; i < m; i++) {
g[U[i]].pb(i);
g[V[i]].pb(i);
}
vector<int32_t> vectudoa(m,0);
int tudoa = ask(vectudoa);
int path = tudoa/A;
int edgein = -1;
int lbs,rbs;
vector<int32_t> vectoll(m,0);
lbs = 0;
rbs = m-1;
while(lbs <= rbs) {
int mid = (lbs+rbs)/2;
vectoll.clear(); vectoll.resize(m,0);
for(int i = 0; i <= mid; i++) {
vectoll[i] = 1;
}
int toll = ask(vectoll);
if(toll != tudoa) {
edgein = mid;
rbs = mid-1;
}
else {
lbs = mid+1;
}
}
assert(edgein != -1);
int ss = U[edgein];
int tt = V[edgein];
vector<pair<int,int>> d(n+10,mp(inf,0));
d[ss] = mp(0,ss); par[ss] = -1; parid[ss] = -1;
d[tt] = mp(0,tt); par[tt] = -1; parid[tt] = -1;
queue<int> q;
while(q.size()) {
int u = q.front(); q.pop();
for(auto id : g[u]) {
int v = U[id]+V[id]-u;
if(d[v].fr > d[u].fr+1) {
d[v] = mp(d[u].fr+1,d[u].sc);
par[v] = u;
parid[v] = id;
q.push(v);
}
}
}
vector<pair<int,int>> Ds;
for(int i = 0; i < n; i++) {
if(d[i].sc == ss) {
Ds.pb(mp(d[i].fr,i));
}
}
sort(all(Ds));
lbs = 0;
rbs = (int) Ds.size()-1;
int32_t s = -1;
while(lbs <= rbs) {
int mid = (lbs+rbs)/2;
vectoll.clear(); vectoll.resize(m,0);
for(int i = 0; i <= mid; i++) {
if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 0;
}
for(int i = mid+1; i < (int) Ds.size(); i++) {
if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
}
int toll = ask(vectoll);
if(toll == tudoa) {
s = Ds[mid].sc;
rbs = mid-1;
}
else {
lbs = mid+1;
}
}
vector<pair<int,int>> Dt;
for(int i = 0; i < n; i++) {
if(d[i].sc == tt) {
Dt.pb(mp(d[i].fr,i));
}
}
sort(all(Dt));
lbs = 0;
rbs = (int) Dt.size()-1;
int32_t t = -1;
while(lbs <= rbs) {
int mid = (lbs+rbs)/2;
vectoll.clear(); vectoll.resize(m,0);
for(int i = 0; i <= mid; i++) {
if(parid[Dt[i].sc] != -1) vectoll[parid[Dt[i].sc]] = 0;
}
for(int i = mid+1; i < (int) Dt.size(); i++) {
if(parid[Dt[i].sc] != -1) vectoll[parid[Dt[i].sc]] = 1;
}
int toll = ask(vectoll);
if(toll == tudoa) {
t = Dt[mid].sc;
rbs = mid-1;
}
else {
lbs = mid+1;
}
}
// cout << ss << " " << tt << endl;
// cout << s << " " << t << endl;
answer(s,t);
}
Compilation message
highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:36:6: warning: unused variable 'path' [-Wunused-variable]
36 | int path = tudoa/A;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2420 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2384 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
3024 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2384 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
3196 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
3124 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
