#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;
vector<vector<pi> > a(N);
vector<pi> pos;
vector<pi> par(N);
void dfs(int s, int e, int cur, int f){
if(cur == f){
pos.push_back({par[s].S,s});
return;
}
for(auto x : a[s]){
if(x.F == e)continue;
par[x.F] = {s,x.S};
dfs(x.F,s,cur+1,f);
}
}
void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
int i;
int m = u.size();
for(i=0;i<m;i++){
a[v[i]].push_back({u[i],i});
a[u[i]].push_back({v[i],i});
}
vector<int> w(m,0);
ll d = ask(w);
int dep = d/A;
int l = 0,r = n-2;
while(l < r){
int mid = (l+r)/2;
for(i=0;i<=mid;i++){
w[i] = 1;
}
ll res = ask(w);
for(i=0;i<=mid;i++){
w[i] = 0;
}
if(res != d){
r = mid;
}
else{
l = mid+1;
}
}
int S = r;
l = 1,r = n-1;
while(l < r){
int mid = (l+r+1)/2;
for(i=n-1;i>=mid;i--){
w[i-1] = 1;
}
ll res = ask(w);
for(i=n-1;i>=mid;i--){
w[i-1] = 0;
}
if(res != d){
l = mid;
}
else{
r = mid-1;
}
}
int E = l;
cerr<<S<<" "<<E<<endl;
answer(S,E);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:43:9: warning: unused variable 'dep' [-Wunused-variable]
43 | int dep = d/A;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
9680 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
9680 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10216 KB |
Output is correct |
2 |
Correct |
55 ms |
10708 KB |
Output is correct |
3 |
Correct |
38 ms |
11216 KB |
Output is correct |
4 |
Correct |
101 ms |
14268 KB |
Output is correct |
5 |
Correct |
61 ms |
14268 KB |
Output is correct |
6 |
Correct |
67 ms |
14348 KB |
Output is correct |
7 |
Correct |
69 ms |
14268 KB |
Output is correct |
8 |
Correct |
73 ms |
14272 KB |
Output is correct |
9 |
Correct |
67 ms |
14268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
9680 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
10312 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
10292 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |