// In The Name Of God
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define pp pop_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define nl '\n'
#define ioi exit(0);
typedef long long ll;
const int MAX_N = (int)1e5 + 7;
const int INF = (int)1e9 + 7;
int n, m, A, B;
vector <int> V, U;
vector < pair <int, int > > g[MAX_N];
namespace Tree {
int depth;
ll min_len;
int dep[MAX_N];
vector <int> e;
bool was[MAX_N];
void bfs(int v = 0, int p = -1, int lvl = 0) {
dep[v] = 0;
was[v] = 1;
queue <int> q;
q.push(v);
while (sz(q)) {
int x = q.front();
q.pop();
for (auto to : g[x]) {
if (!was[to.f]) {
dep[to.f] = dep[x] + 1;
was[to.f] = 1;
q.push(to.f);
if (dep[x] + 1 == depth) {
// e.pb(to.s);
}
}
}
}
/// -------------------------
/*return;
for (auto to : g[v]) {
if (to.f != p) {
dfs(to.f, v, lvl + 1);
if (lvl + 1 == depth) {
e.pb(to.s);
}
}
}*/
}
int id(const vector <int> &x) {
if (sz(x) == 1) return x[0];
int mid = sz(x) / 2;
vector <int> q(m, 0), sol;
rep(i, 0, mid - 1) {
q[x[i]] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
if (cur > min_len) return id(sol);
vector <int> on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return id(on);
}
void solve(int S = 0) {
// if (n != m + 1) return;
{
vector <int> q(m, 0);
min_len = ask(q);
depth = min_len / A;
}
bfs(S);
rep(i, 0, n) {
for (auto to : g[i]) {
if (min(dep[i], dep[to.f]) + 1 == depth) {
e.pb(to.s);
}
}
}
int ed = id(e);
rep(i, 0, n - 1) {
for (auto it : g[i]) {
if (it.s == ed) {
if (dep[i] > dep[it.f]) answer(S, i);
else answer(S, it.f);
return;
}
}
}
assert(0);
}
}
namespace FindS {
int dist;
int dep[MAX_N];
vector <int> edges[MAX_N];
bool was[MAX_N];
void bfs(int v = 0, int p = -1, int lvl = 0) {
dep[v] = 0;
was[v] = 1;
queue <int> q;
q.push(v);
while (sz(q)) {
int x = q.front();
q.pop();
for (auto to : g[x]) {
if (!was[to.f]) {
dep[to.f] = dep[x] + 1;
was[to.f] = 1;
q.push(to.f);
}
}
}
// ------------------------
/*return;
for (auto to : g[v]) {
if (to.f != p) {
dfs(to.f, v, lvl + 1);
edges[lvl].pb(to.s);
}
}*/
}
int id1(const vector <int> &x) {
if (sz(x) == 1) return x[0];
int mid = sz(x) / 2;
vector <int> q(m, 0), sol;
rep(i, 0, mid - 1) {
q[x[i]] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
if (cur > dist * A) return id1(sol);
vector <int> on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return id1(on);
}
int NeedLen;
int id(vector < pair <int, vector <int> > > x) {
if (sz(x) == 1) {
if (1) cerr << " -> " << x[0].f << endl;
vector <int> ind;
for (auto it : g[x[0].f]) {
// ind.pb(it);
// cerr << min(dep[x[0].f], dep[it.f]) << ' ' << it.s << ' ' << NeedLen << endl;
if (min(dep[x[0].f], dep[it.f]) == NeedLen) ind.pb(it.s);
}
// ioi
return id1(ind);
}
int mid = sz(x) / 2;
vector <int> q(m, 0);
vector < pair <int, vector <int> > > sol;
rep(i, 0, mid - 1) {
for (auto it : g[x[i].f]) q[it.s] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
// cerr << sz(sol) << ' ' << sol[0].f << ' ' << cur << endl;
if (cur > (ll)dist * A) return id(sol);
vector < pair <int, vector <int> > > on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return id(on);
}
bool check(int x) {
vector <int> q(m, 0);
for (auto to : g[x]) q[to.s] = 1;
return ask(q) == (ll)(dist - 1) * A + B;
}
int GetS() {
{
vector <int> q(m, 0);
dist = ask(q) / A;
}
// dist of path
bfs(0);
rep(i, 0, n) {
for (auto to : g[i]) {
edges[min(dep[i], dep[to.f])].pb(to.s);
}
}
int l = 0, r = n, res = -1;
while (l <= r) {
int mid = l + r >> 1;
vector <int> q(m, 0);
rep(i, 0, mid) for (auto ind : edges[i]) q[ind] = 1;
ll cur = ask(q);
if (cur == (ll)dist * B) res = mid, r = mid - 1;
else l = mid + 1;
}
if (res == -1) {
if (0) cerr << "DIDN't FIND DEPTH of S" << endl;
}
assert(res != -1);
// found depth of S
{
map <int, vector <int > > edge_tov;
for (auto i : edges[res]) {
int x = V[i], y = U[i];
if (dep[x] > dep[y]) swap(x, y);
edge_tov[y].pb(i);
// cerr << V[i] << ' ' << U[i] << " -> " << y << endl;
if (dep[x] == dep[y]) edge_tov[x].pb(i);
}
vector < pair <int, vector <int > > > X;
for (auto it : edge_tov) {
X.pb(it);
}
NeedLen = res;
int ind = id(X);
// cerr <<
// cerr << ind << endl;
if (0) cerr << V[ind] << ' ' << U[ind] << endl;
if (check(V[ind])) return V[ind];
return U[ind];
}
// found S
if (0) cerr << "DIDN'T FIND S" << endl;
assert(0);
}
}
void find_pair(int N, vector<int> _U, vector<int> _V, int _A, int _B) {
n = N;
m = sz(_U);
A = _A;
B = _B;
V = _V;
U = _U;
rep(i, 0, m - 1) {
g[V[i]].pb({U[i], i});
g[U[i]].pb({V[i], i});
}
// copy finished
int S = FindS :: GetS();
if (0) cerr << S << endl;
Tree :: solve(S);
return;
answer(0, N - 1);
}
Compilation message
highway.cpp: In function 'int FindS::GetS()':
highway.cpp:233:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5116 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
5880 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5092 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
6496 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
6908 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
