| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1068112 | Ignut | 통행료 (IOI18_highway) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Ignut
#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 maxDepth = 0;
void dfs(int v, int par, int d) {
depth[v] = d;
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;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
w.assign(M, 0);
for (int i = 0; i < M; i ++) {
int d = max(depth[U[i]], depth[V[i]]);
if (d <= mid)
w[i] = true;
}
ll val = ask(w);
if (val == da)
lo = mid;
else
hi = 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();
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);
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]];
// 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 (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;
}
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]];
}
answer(u, v);
return;
}