| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 414451 | Temmie | Highway Tolls (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "highway"
#include <bits/stdc++.h>
typedef long long ll;
//ll ask(std::vector <int> v) {
//return 0;
//}
//void answer(int s, int t) {
//std::cerr << "answered: (" << s << ", " << t << ")" << std::endl;
//}
void find_pair(int n, std::vector <int> U, std::vector <int> V, int A, int B) {
assert((int)U.size() == n - 1); // only tree subtasks
// ( index of nieghbor, index of edge in U/V )
std::vector <std::vector <std::pair <int, int>>> g(n);
for (int i = 0; i < n - 1; i++) {
g[U[i]].push_back({ V[i], i });
g[V[i]].push_back({ U[i], i });
}
std::pair <int, int> ans = { -1, -1 };
int root1 = -1, root2 = -1;
ll whole = ask({ });
{
int l = 0, r = n - 1;
int best = n;
while (l <= r) {
int mid = (l + r) >> 1;
std::vector <int> v(n - 1, 0);
for (int i = l; i <= mid; i++ ) {
v[i] = 1;
}
ll now = ask(v);
if (now > whole) {
// contains at least one edge of path
best = mid;
r = mid - 1;
} else {
// contains no edges of path
l = mid + 1;
}
}
assert(best != n);
root1 = U[best];
root2 = V[best];
}
{
int root = root1;
int otherroot = root2;
std::vector <int> wholeTree(n - 1, 0);
std::queue <std::pair <int, int>> q; // ( node, par )
q.push({ root, otherroot });
std::vector <int> dep(n, -1);
dep[root] = 0;
std::vector <int> edgeUp(n, -1);
while (q.size()) {
auto p = q.front(); q.pop();
for (auto x : g[p.first]) if (x.first != p.second) {
wholeTree[x.second] = 1;
q.push({ x.first, p.first });
dep[x.first] = dep[p.first] + 1;
edgeUp[x.first] = x.second;
}
}
ll query = ask(wholeTree);
int depthWanted = (query - whole) / ll(B);
assert(depthWanted >= 0);
if (depthWanted == 0) {
// root is also ans
ans.first = root;
}
// ( node, edge up )
std::vector <std::pair <int, int>> possible;
for (int i = 0; i < n; i++) {
if (dep[i] == depthWanted) {
assert(edgeUp[i] != -1);
possible.emplace_back(i, edgeUp[i]);
}
}
int l = 0, r = (int)possible.size() - 1;
int best = possible.size();
while (l <= r) {
int mid = (l + r) >> 1;
std::vector <int> v(n - 1, 0);
for (int i = l; i <= mid; i++) {
v[possible[i].second] = 1;
}
ll now = ask(v);
if (now == whole) {
// inside
best = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
assert(best != (int)possible.size());
ans.first = possible[best].first;
}
{
int root = root1;
int otherroot = root2;
std::swap(root, otherroot);
std::vector <int> wholeTree(n - 1, 0);
std::queue <std::pair <int, int>> q; // ( node, par )
q.push({ root, otherroot });
std::vector <int> dep(n, -1);
dep[root] = 0;
std::vector <int> edgeUp(n, -1);
while (q.size()) {
auto p = q.front(); q.pop();
for (auto x : g[p.first]) if (x.first != p.second) {
wholeTree[x.second] = 1;
q.push({ x.first, p.first });
dep[x.first] = dep[p.first] + 1;
edgeUp[x.first] = x.second;
}
}
ll query = ask(wholeTree);
int depthWanted = (query - whole) / ll(B);
assert(depthWanted >= 0);
if (depthWanted == 0) {
// root is also ans
ans.second = root;
}
// ( node, edge up )
std::vector <std::pair <int, int>> possible;
for (int i = 0; i < n; i++) {
if (dep[i] == depthWanted) {
assert(edgeUp[i] != -1);
possible.emplace_back(i, edgeUp[i]);
}
}
int l = 0, r = (int)possible.size() - 1;
int best = possible.size();
while (l <= r) {
int mid = (l + r) >> 1;
std::vector <int> v(n - 1, 0);
for (int i = l; i <= mid; i++) {
v[possible[i].second] = 1;
}
ll now = ask(v);
if (now == whole) {
// inside
best = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
assert(best != (int)possible.size());
ans.second = possible[best].first;
}
answer(ans.first, ans.second);
}
//int main() {
//}