이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define int long long
#define pii pair<long long, long long>
void find_pair(signed n, vector<signed> U, vector<signed> V, signed A, signed B) {
vector<int> p(n, -1), e(n, -1);
vector<bool> leaf(n, 1);
for (int i = 0; i < n - 1; i++) {
int u = min(U[i], V[i]), v = max(U[i], V[i]);
leaf[u] = 0;
p[v] = u;
e[v] = i;
}
int k = 0;
vector<int> leaves;
for (int i = 0; i < n; i++) {
if (leaf[i]) {
leaves.push_back(i);
k++;
}
}
cout << "\n";
vector<signed> w(n - 1);
int zero = ask(w);
int dist = zero / A;
int l = -1, r = k;
while (r - l > 1) {
int md = (l + r) / 2;
vector<signed> w(n - 1);
for (int i = 0; i < md; i++) {
int v = leaves[i];
while (p[v] != -1 && !w[e[v]]) {
w[e[v]] = 1;
v = p[v];
}
}
if (ask(w) == zero) l = md;
else r = md;
}
int v = leaves[l];
int vdist = 0;
while (p[v] != -1) {
v = p[v];
vdist++;
}
v = leaves[l];
for (int i = 0; i < vdist - dist; i++) {
v = p[v];
}
answer(0, v);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |