// 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 parent[MAXN];
int maxDepth = 0;
void dfs(int v, int par, int d) {
depth[v] = d;
parent[v] = par;
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;
// cerr << "from " << lo << " to " << hi << '\n';
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);
// cerr << mid << " : " << val << " vs " << da + 1ll * (du - mid) * (B - A) << '\n';
if (val == da + 1ll * (du - mid) * (B - A))
hi = mid;
else
lo = 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() - 1;
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);
// cerr << mid << " : " << val << " vs " << da << '\n';
// for (int val : w) cerr << val;
// cerr << '\n';
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]];
// for (int ind : eu) {
// cerr << U[ind] << " -> " << V[ind] << '\n';
// }
// cerr << "U = " << u << "(" << lo << ")\n";
// cerr << du << ' ' << dv << ' ' << dist << '\n';
int bad = u;
while (depth[bad] > dv) bad = parent[bad];
// 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 (U[i] == bad || V[i] == bad) continue;
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;
}
// cerr << lo << " -- " << hi << '\n';
// answer(-1, -1); return;
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]];
// for (int ind : ev) {
// cerr << U[ind] << " -> " << V[ind] << '\n';
// }
// cerr << "V = " << v << "(" << lo << ")\n";
}
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
N M A B S T
tree:
4 3 1 2 3 2
0 1
0 2
1 3
*/
// namespace {
// constexpr int MAX_NUM_CALLS = 100;
// constexpr long long INF = 1LL << 61;
// int N, M, A, B, S, T;
// std::vector<int> U, V;
// std::vector<std::vector<std::pair<int, int>>> graph;
// bool answered, wrong_pair;
// int num_calls;
// int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
// }
// void wrong_answer(const char *MSG) {
// printf("Wrong Answer: %s\n", MSG);
// exit(0);
// }
// } // namespace
// long long ask(const std::vector<int> &w) {
// if (++num_calls > MAX_NUM_CALLS) {
// wrong_answer("more than 100 calls to ask");
// }
// if (w.size() != (size_t)M) {
// wrong_answer("w is invalid");
// }
// for (size_t i = 0; i < w.size(); ++i) {
// if (!(w[i] == 0 || w[i] == 1)) {
// wrong_answer("w is invalid");
// }
// }
// std::vector<bool> visited(N, false);
// std::vector<long long> current_dist(N, INF);
// std::queue<int> qa, qb;
// qa.push(S);
// current_dist[S] = 0;
// while (!qa.empty() || !qb.empty()) {
// int v;
// if (qb.empty() ||
// (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
// v = qa.front();
// qa.pop();
// } else {
// v = qb.front();
// qb.pop();
// }
// if (visited[v]) {
// continue;
// }
// visited[v] = true;
// long long d = current_dist[v];
// if (v == T) {
// return d;
// }
// for (auto e : graph[v]) {
// int vv = e.first;
// int ei = e.second;
// if (!visited[vv]) {
// if (w[ei] == 0) {
// if (current_dist[vv] > d + A) {
// current_dist[vv] = d + A;
// qa.push(vv);
// }
// } else {
// if (current_dist[vv] > d + B) {
// current_dist[vv] = d + B;
// qb.push(vv);
// }
// }
// }
// }
// }
// return -1;
// }
// void answer(int s, int t) {
// if (answered) {
// wrong_answer("answered not exactly once");
// }
// if (!((s == S && t == T) || (s == T && t == S))) {
// wrong_pair = true;
// }
// answered = true;
// }
// int main() {
// N = read_int();
// M = read_int();
// A = read_int();
// B = read_int();
// S = read_int();
// T = read_int();
// U.resize(M);
// V.resize(M);
// graph.assign(N, std::vector<std::pair<int, int>>());
// for (int i = 0; i < M; ++i) {
// U[i] = read_int();
// V[i] = read_int();
// graph[U[i]].push_back({V[i], i});
// graph[V[i]].push_back({U[i], i});
// }
// answered = false;
// wrong_pair = false;
// num_calls = 0;
// find_pair(N, U, V, A, B);
// if (!answered) {
// wrong_answer("answered not exactly once");
// }
// if (wrong_pair) {
// wrong_answer("{s, t} is wrong");
// }
// printf("Accepted: %d\n", num_calls);
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2904 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3404 KB |
Output is correct |
| 3 |
Correct |
75 ms |
8036 KB |
Output is correct |
| 4 |
Correct |
73 ms |
8132 KB |
Output is correct |
| 5 |
Correct |
83 ms |
8040 KB |
Output is correct |
| 6 |
Correct |
72 ms |
7956 KB |
Output is correct |
| 7 |
Correct |
66 ms |
8472 KB |
Output is correct |
| 8 |
Correct |
73 ms |
8044 KB |
Output is correct |
| 9 |
Correct |
75 ms |
7948 KB |
Output is correct |
| 10 |
Correct |
71 ms |
7932 KB |
Output is correct |
| 11 |
Correct |
87 ms |
8852 KB |
Output is correct |
| 12 |
Correct |
109 ms |
9348 KB |
Output is correct |
| 13 |
Correct |
88 ms |
8952 KB |
Output is correct |
| 14 |
Correct |
81 ms |
8532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
15 ms |
4644 KB |
Output is correct |
| 3 |
Correct |
27 ms |
5720 KB |
Output is correct |
| 4 |
Correct |
87 ms |
12280 KB |
Output is correct |
| 5 |
Correct |
64 ms |
12048 KB |
Output is correct |
| 6 |
Correct |
62 ms |
12060 KB |
Output is correct |
| 7 |
Correct |
66 ms |
11948 KB |
Output is correct |
| 8 |
Correct |
71 ms |
12516 KB |
Output is correct |
| 9 |
Correct |
78 ms |
12064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3160 KB |
Output is correct |
| 3 |
Incorrect |
55 ms |
6692 KB |
Output is incorrect: {s, t} is wrong. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
222 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
222 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
