// 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);
}
}
}
}
int GetT(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) {
for (auto to : g[x[i]]) q[to.s] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
if (cur > min_len) return GetT(sol);
vector <int> on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return GetT(on);
}
void solve(int S = 0) {
{
vector <int> q(m, 0);
min_len = ask(q);
depth = min_len / A;
}
bfs(S);
rep(i, 0, n - 1) {
if (dep[i] == depth) {
e.pb(i);
}
}
int T = GetT(e);
// cerr << S << ' ' << T << endl;
answer(S, T);
}
}
namespace FindS {
int dist;
int dep[MAX_N];
bool was[MAX_N];
void bfs(int v = 0) {
queue <int> q;
memset(was, 0, sizeof(was));
dep[v] = 0;
was[v] = 1;
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);
}
}
}
}
int FindV(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) {
for (auto to : g[x[i]]) q[to.s] = 1;
sol.pb(x[i]);
}
// if (0) cerr << sz(x) << endl;
assert(sz(sol));
ll cur = ask(q);
if (cur > (ll)dist * A) return FindV(sol);
vector <int> on;
rep(i, mid, sz(x) - 1) on.pb(x[i]);
return FindV(on);
}
int GetS() {
{
vector <int> q(m, 0);
dist = ask(q) / A;
}
// dist of path
int C = -1;
{
bfs();
int l = 0, r = n, res = -1;
while (l <= r) {
int mid = l + r >> 1;
vector <int> q(m, 0);
rep(i, 0, n - 1) if (dep[i] <= mid) for (auto it : g[i]) q[it.s] = 1;
ll cur = ask(q);
if (cur > (ll)dist * A) res = mid, r = mid - 1;
else l = mid + 1;
}
assert(res != -1);
vector <int> x;
rep(i, 0, n - 1) if (dep[i] == res) x.pb(i);
C = FindV(x);
}
// Found dist to first vertex on path S, T and that vertex
int S = -1;
{
bfs(C);
// cerr << "Start -> " << C << endl;
// rep(i, 0, n - 1) cerr << dep[i] << ' ' << i << endl;
int l = 0, r = n, res = -1;
while (l <= r) {
int mid = l + r >> 1;
vector <int> q(m, 0);
rep(i, 0, n - 1) if (dep[i] <= mid) for (auto it : g[i]) if (dep[it.f] <= mid) q[it.s] = 1;
ll cur = ask(q);
if (cur == (ll)dist * B) res = mid, r = mid - 1;
else l = mid + 1;
}
assert(res != -1);
vector <int> x;
rep(i, 0, n - 1) if (dep[i] == res) x.pb(i);
// for (auto it : x) cerr << it << ' ';
S = FindV(x);
}
// Found S
// cerr << S << endl;
return S;
}
}
/*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);
}
}
}
}
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 S = -1;
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 id(vector < pair <int, vector <int> > > x) {
if (sz(x) == 1) {
if (check(x[0].f)) {
S = x[0].f;
cerr << "X[0].f is optimal" << ' ' << x[0].f << ' ' << check(x[0].f) << endl;
}
if (0) 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);
}
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) {
if (0) cerr << it.f << endl;
X.pb(it);
}
NeedLen = res;
int ind = id(X);
cerr << S << endl;
if (S != -1)
// 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:154:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
highway.cpp:174:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2768 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2764 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2640 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2684 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 12 |
Runtime error |
4 ms |
2728 KB |
Execution killed with signal 2 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
30 ms |
3816 KB |
Output is correct |
| 3 |
Incorrect |
389 ms |
13796 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
43 ms |
4088 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4904 KB |
Output is correct |
| 4 |
Correct |
188 ms |
8740 KB |
Output is correct |
| 5 |
Correct |
171 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
190 ms |
8812 KB |
Output is correct |
| 7 |
Correct |
171 ms |
8848 KB |
Output is correct |
| 8 |
Correct |
215 ms |
8752 KB |
Output is correct |
| 9 |
Correct |
191 ms |
8872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
33 ms |
4016 KB |
Output is correct |
| 3 |
Correct |
247 ms |
10268 KB |
Output is correct |
| 4 |
Incorrect |
412 ms |
12908 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
4004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3904 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
