#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
void answer(int s, int t);
ll ask(const vector<int> &w);
struct edge {
int to, i;
edge() {}
edge(int tt, int ii) {
to = tt;
i = ii;
}
};
vector<int> w;
vector<int> ord;
vector<int> special;
int n, m;
ll d;
vector<vector<edge>> g;
vector<int> vis, dep;
int crit;
ll f(int x) {
for (int i = 0; i < x; i++) w[ord[i]] = 0;
for (int i = x; i < ord.size(); i++) w[ord[i]] = 1;
return ask(w);
}
void bfs(int v) {
ord.clear();
vis.resize(n, 0);
dep.resize(n, 0);
vis[v] = 1;
queue<int> q;
q.push(v);
while (!q.empty()) {
int x = q.front();
q.pop();
for (const auto &i : g[x])
if (!vis[i.to]) {
dep[i.to] = dep[x] + 1;
ord.push_back(i.i);
vis[i.to] = 1;
q.push(i.to);
}
}
}
void dfs(int v) {
vis[v] = 1;
for (const auto &i : g[v])
if (!vis[i.to] && w[i.i] == 0) {
special[i.i] = 1;
dfs(i.to);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
if (N == 2) {
answer(0, 1);
return;
}
n = N;
g.resize(n);
m = U.size();
w.resize(m);
for (int i = 0; i < m; i++) {
g[U[i]].push_back(edge(V[i], i));
g[V[i]].push_back(edge(U[i], i));
}
for (auto &i : w) i = 0;
d = ask(w);
if (OO) cout << "d = " << d << '\n';
int lo, hi, mid;
// 1: find edge on shortest path
ord.resize(m);
for (int i = 0; i < m; i++) ord[i] = i;
lo = 0, hi = m - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (f(mid) == d) hi = mid - 1;
else lo = mid + 1;
}
crit = lo;
if (OO) cout << "critical edge index " << crit << ", (" << U[crit] << ", " << V[crit] << ")\n";
// 2: root at 1 end of the edge, and bsearch in the subtree of the other for S/T
for (auto &i : w) i = 1;
bfs(U[crit]);
for (auto &i : ord) w[i] = 0;
// determine all edges in the subtree of the other end
for (auto &i : vis) i = 0;
vis[U[crit]] = 1;
special.resize(m, 0);
special[crit] = 1;
dfs(V[crit]);
vector<int> ord1, ord2;
for (const auto &i : ord)
if (special[i])
ord1.push_back(i);
else
ord2.push_back(i);
if (OO) {
cout << "rooted at " << U[crit] << '\n';
cout << "bfs: ";
for (const auto &i : ord) cout << i << " "; cout << '\n';
cout << "ord1: ";
for (const auto &i : ord1) cout << i << " "; cout << '\n';
cout << "ord2: ";
for (const auto &i : ord2) cout << i << " "; cout << '\n';
cout << "dep: ";
for (const auto &i : dep) cout << i << " "; cout << '\n';
}
// bsearch in the subtree
ord = ord1;
lo = 0, hi = (int)ord.size() - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (f(mid) == d) hi = mid - 1;
else lo = mid;
}
int S, T;
if (OO) {
cout << "first bsearch yields edge " << ord[lo] << '\n';
}
if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) S = U[ord[lo]];
else S = V[ord[lo]];
if (OO) cout << "resulting in S = " << S << '\n';
if ((ll)A * dep[S] == d) {
T = U[crit];
answer(S, T);
return;
}
// bsearch on everything else
for (auto &i : ord1) w[i] = 0;
ord = ord2;
lo = 0, hi = (int)ord.size() - 1;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (f(mid) == d) hi = mid - 1;
else lo = mid;
}
if (OO) {
cout << "second bsearch yields edge " << ord[lo] << '\n';
}
if (dep[U[ord[lo]]] > dep[V[ord[lo]]]) T = U[ord[lo]];
else T = V[ord[lo]];
if (OO) cout << "resulting in T = " << T << '\n';
answer(S, T);
}
Compilation message
highway.cpp: In function 'll f(int)':
highway.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = x; i < ord.size(); i++) w[ord[i]] = 1;
~~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:120:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : ord) cout << i << " "; cout << '\n';
^~~
highway.cpp:120:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : ord) cout << i << " "; cout << '\n';
^~~~
highway.cpp:122:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : ord1) cout << i << " "; cout << '\n';
^~~
highway.cpp:122:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : ord1) cout << i << " "; cout << '\n';
^~~~
highway.cpp:124:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : ord2) cout << i << " "; cout << '\n';
^~~
highway.cpp:124:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : ord2) cout << i << " "; cout << '\n';
^~~~
highway.cpp:126:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : dep) cout << i << " "; cout << '\n';
^~~
highway.cpp:126:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : dep) cout << i << " "; cout << '\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
328 KB |
Output is incorrect: {s, t} is wrong. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
396 KB |
Output is correct |
| 2 |
Correct |
23 ms |
1280 KB |
Output is correct |
| 3 |
Incorrect |
192 ms |
9540 KB |
Output is incorrect: {s, t} is wrong. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1504 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
2652 KB |
Output is incorrect: {s, t} is wrong. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
400 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
1308 KB |
Output is incorrect: {s, t} is wrong. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1344 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
1344 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
