| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1211275 | SpyrosAliv | Highway Tolls (IOI18_highway) | C++20 | 0 ms | 0 KiB |
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<int, int>>> tree;
vector<int> par, dep, edgeLab;
int n, a, b, maxD;
void prec(int node, int p = 0, int d = 0) {
par[node] = p;
dep[node] = d;
maxD = max(maxD, d);
for (auto [next, lab]: tree[node]) {
if (next == p) continue;
edgeLab[next] = lab;
prec(next, node, d+1);
}
}
int find_second(int root) {
par.assign(n, 0);
dep.assign(n, 0);
edgeLab.assign(n, 0);
maxD = 0;
prec(root, 0);
vector<int> q;
q.assign(n-1, 0);
ll init = ask(q);
int lo = 1, hi = maxD;
int secDep = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
fill(q.begin(), q.end(), 0);
for (int i = 0; i < n; i++) {
if (dep[i] >= mid) {
q[edgeLab[i]] = 1;
}
}
ll ret = ask(q);
if (ret != init) {
secDep = mid;
lo = mid+1;
}
else hi = mid-1;
}
vector<int> cands;
for (int i = 0; i < n; i++) {
if (dep[i] == secDep) cands.push_back(i);
}
int sz = cands.size();
lo = 0, hi = sz-1;
int fin = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
fill(q.begin(), q.end(), 0);
for (int i = 0; i <= mid; i++) {
q[edgeLab[cands[i]]] = 1;
}
ll ret = ask(q);
if (ret != init) {
fin = mid;
hi = mid-1;
}
else lo = mid+1;
}
return cands[fin];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
n = N;
tree.clear();
tree.resize(n);
for (int i = 0; i < n-1; i++) {
tree[U[i]].push_back(V[i]);
tree[V[i]].push_back(U[i]);
}
a = A;
b = B;
answer(0, find_second(0));
}