#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
const ll N = 1e5 + 5;
vector < ii > v[N];
ii edge[N]; ll in[N]; ll par[N];
ll n, m;
vector < ll > all;
void dfs(ll s, ll p){
par[s] = p;
for(auto [u, i] : v[s]){
if(u - p){
dfs(u, s);
in[i] = all.size();
all.pb(i);
edge[i] = {s, u};
}
}
return;
}
ll query(ll l, ll r){
vector < int > w(m, 0);
if(r == -1) return ask(w);
for(ll i = l; i <= r; i++) w[all[i]] = 1;
return ask(w);
}
vector < ll > collect;
void DFS(ll s, ll p){
for(auto [u, i] : v[s]){
if(u - p){
DFS(u, s);
collect.pb(i);
}
}
return;
}
void find_pair(int _n, std::vector<int> U, std::vector<int> V, int A, int B) {
n = _n, m = U.size();
for(ll i = 0; i < m; i++){
ll x = V[i], y = U[i];
v[x].pb({y, i});
v[y].pb({x, i});
}
dfs(0, -1);
ll cost = query(0, -1);
ll lo = 0, hg = m - 1;
ll X = 0, root = 0, Y = 0;
while(lo <= hg){
ll mid = (lo + hg)/2;
ll k = query(0, mid);
if(k == cost){
lo = mid + 1;
}else{
X = mid;
hg = mid - 1;
}
}
lo = 0, hg = m - 1;
while(lo <= hg){
ll mid = (lo + hg)/2;
ll k = query(mid, m-1);
if(k == cost){
hg = mid - 1;
}else{
root = mid;
lo = mid + 1;
}
}
//return;
ll _X = edge[all[X]].ss;
ll _R = edge[all[root]].ff;
DFS(edge[all[root]].ss, _R);
collect.pb(root);
sort(collect.begin(), collect.end());
ll L = collect[0], R = collect.back();
lo = L, hg = R;
while(lo <= hg){
ll mid = (lo + hg)/2;
ll k = query(L, mid);
if(k == cost){
lo = mid + 1;
}else{
hg = mid - 1;
Y = mid;
}
}
ll _Y = edge[all[Y]].ss;
int S,T;
if(_X == _Y) S = _X, T = _R;
else S = _X, T = _Y;
// cout << _X << ' ' << _R << ' ' << _Y << '\n';
answer(S, T);
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2680 KB |
Output is correct |
2 |
Correct |
2 ms |
2640 KB |
Output is correct |
3 |
Correct |
2 ms |
2640 KB |
Output is correct |
4 |
Correct |
2 ms |
2640 KB |
Output is correct |
5 |
Correct |
1 ms |
2640 KB |
Output is correct |
6 |
Correct |
2 ms |
2640 KB |
Output is correct |
7 |
Correct |
2 ms |
2640 KB |
Output is correct |
8 |
Correct |
2 ms |
2640 KB |
Output is correct |
9 |
Correct |
2 ms |
2640 KB |
Output is correct |
10 |
Correct |
2 ms |
2640 KB |
Output is correct |
11 |
Correct |
1 ms |
2640 KB |
Output is correct |
12 |
Correct |
2 ms |
2676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2768 KB |
Output is correct |
2 |
Correct |
13 ms |
3992 KB |
Output is correct |
3 |
Correct |
132 ms |
14112 KB |
Output is correct |
4 |
Correct |
144 ms |
14044 KB |
Output is correct |
5 |
Correct |
150 ms |
14056 KB |
Output is correct |
6 |
Correct |
172 ms |
14156 KB |
Output is correct |
7 |
Correct |
178 ms |
14096 KB |
Output is correct |
8 |
Correct |
162 ms |
14064 KB |
Output is correct |
9 |
Correct |
184 ms |
14052 KB |
Output is correct |
10 |
Correct |
138 ms |
14120 KB |
Output is correct |
11 |
Correct |
134 ms |
15844 KB |
Output is correct |
12 |
Correct |
156 ms |
17564 KB |
Output is correct |
13 |
Correct |
180 ms |
16808 KB |
Output is correct |
14 |
Correct |
173 ms |
14908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
4936 KB |
Output is correct |
2 |
Correct |
32 ms |
7092 KB |
Output is correct |
3 |
Incorrect |
46 ms |
9204 KB |
Output is incorrect: {s, t} is wrong. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2768 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
173 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
172 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |