// Ignut
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ll ask(vector<int> w);
// void answer(int s, int t);
const int MAXN = 9e4 + 123;
int n;
vector<int> tree[MAXN];
int depth[MAXN];
int maxDepth = 0;
void dfs(int v, int par, int d) {
depth[v] = d;
maxDepth = max(maxDepth, d);
for (int to : tree[v])
if (to != par)
dfs(to, v, d + 1);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
for (int i = 0; i < M; i ++) {
tree[U[i]].push_back(V[i]);
tree[V[i]].push_back(U[i]);
}
dfs(0, -1, 0);
vector<int> w(M, 0);
ll da = ask(w);
int dist = ask(w) / (1ll * A);
// bigger depth -- u
int lo = 0, hi = maxDepth;
int lo2 = 0;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
w.assign(M, 0);
for (int i = 0; i < M; i ++) {
int d = min(depth[U[i]], depth[V[i]]);
if (d >= mid)
w[i] = true;
}
ll val = ask(w);
if (val == 1ll * dist * B)
lo2 = max(lo2, mid);
if (val == da)
hi = mid;
else
lo = mid + 1;
}
int du = lo;
// smaller depth -- v
lo = lo2, hi = du;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
w.assign(M, 0);
for (int i = 0; i < M; i ++) {
int d = max(depth[U[i]], depth[V[i]]);
if (d <= mid)
w[i] = true;
}
ll val = ask(w);
if (val == da)
lo = mid;
else
hi = mid - 1;
}
int dv = lo;
// ========================================================== //
// findind u (lower point)
vector<int> eu;
for (int i = 0; i < M; i ++) {
int d = max(depth[U[i]], depth[V[i]]);
if (d == du)
eu.push_back(i);
}
int hi2 = n - 1;
lo = 0, hi = eu.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
w.assign(M, 0);
for (int i = 0; i < mid; i ++)
w[eu[i]] = true;
ll val = ask(w);
if (val == da - 2 * A + 2 * B)
hi2 = min(hi2, mid);
if (val > da)
hi = mid;
else
lo = mid + 1;
}
int u;
if (depth[U[eu[lo]]] == du) u = U[eu[lo]];
else u = V[eu[lo]];
// finding v
int v;
if (du - dv == dist) {
// just vertical
// look down
vector<int> ev;
for (int i = 0; i < M; i ++) {
int d = min(depth[U[i]], depth[V[i]]);
if (d == dv)
ev.push_back(i);
}
lo = 0, hi = ev.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
w.assign(M, 0);
for (int i = 0; i < mid; i ++)
w[ev[i]] = true;
ll val = ask(w);
if (val > da)
hi = mid;
else
lo = mid + 1;
}
if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
else v = V[ev[lo]];
}
else {
// normal path (lca != u and lca != v)
vector<int> ev;
for (int i = 0; i < M; i ++) {
int d = max(depth[U[i]], depth[V[i]]);
if (d == dv)
ev.push_back(i);
}
lo = 0, hi = ev.size() - 1;
ll needVal = da;
if (du == dv) {
hi = min(int(ev.size()) - 1, hi2);
needVal = needVal - A + B;
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
w.assign(M, 0);
for (int i = 0; i < mid; i ++)
w[ev[i]] = true;
ll val = ask(w);
if (val > needVal)
hi = mid;
else
lo = mid + 1;
}
if (depth[U[ev[lo]]] == dv) v = U[ev[lo]];
else v = V[ev[lo]];
}
answer(u, v);
return;
}
/*
4, [0, 0, 0, 1], [1, 2, 3, 2], 1, 3)
4 4 1 3 1 3
0 1
0 2
0 3
1 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3416 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
233 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
224 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
