#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];
vector<int> 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) {
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;
d[tt] = mp(0,tt); par[tt] = -1;
queue<int> q; q.push(ss); q.push(tt);
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].clear(); parid[v].pb(id);
q.push(v);
}
else if(d[v].fr == d[u].fr+1 && d[v].sc != d[u].sc) {
d[v].sc = -1;
}
else if(d[v].fr == d[u].fr+1) {
parid[v].pb(id);
}
}
}
int toll0;
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;
vectoll.clear(); vectoll.resize(m,1);
for(int i = 0; i < (int) Ds.size(); i++) {
for(auto id : parid[Ds[i].sc]) vectoll[id] = 0;
// if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
}
toll0 = ask(vectoll);
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; i < (int) Ds.size(); i++) {
for(auto id : parid[Ds[i].sc]) vectoll[id] = 1;
// if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
}
int toll = ask(vectoll);
if(toll != tudoa) {
s = Ds[mid].sc;
lbs = mid+1;
}
else {
rbs = 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;
vectoll.clear(); vectoll.resize(m,1);
for(int i = 0; i < (int) Dt.size(); i++) {
for(auto id : parid[Dt[i].sc]) vectoll[id] = 0;
// if(parid[Ds[i].sc] != -1) vectoll[parid[Ds[i].sc]] = 1;
}
toll0 = ask(vectoll);
while(lbs <= rbs) {
int mid = (lbs+rbs)/2;
vectoll.clear(); vectoll.resize(m,1);
// for(int i = 0; i <= mid; i++) {
// if(parid[Dt[i].sc] != -1) vectoll[parid[Dt[i].sc]] = 0;
// }
for(int i = 0; i <= mid; i++) {
for(auto id : parid[Dt[i].sc]) vectoll[id] = 0;
// if(parid[Dt[i].sc] != -1) vectoll[parid[Dt[i].sc]] = 1;
}
int toll = ask(vectoll);
if(toll == toll0) {
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:26:6: warning: unused variable 'path' [-Wunused-variable]
26 | int path = tudoa/A;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4540 KB |
Output is correct |
2 |
Correct |
2 ms |
4432 KB |
Output is correct |
3 |
Correct |
2 ms |
4452 KB |
Output is correct |
4 |
Incorrect |
2 ms |
4432 KB |
Output is incorrect: {s, t} is wrong. |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4596 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
5944 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4560 KB |
Output is correct |
2 |
Correct |
12 ms |
5968 KB |
Output is correct |
3 |
Incorrect |
97 ms |
14808 KB |
Output is incorrect: {s, t} is wrong. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
6040 KB |
Output is correct |
2 |
Correct |
19 ms |
6108 KB |
Output is correct |
3 |
Correct |
125 ms |
17492 KB |
Output is correct |
4 |
Incorrect |
163 ms |
17472 KB |
Output is incorrect: {s, t} is wrong. |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
5888 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |