제출 #1041458

#제출 시각아이디문제언어결과실행 시간메모리
1041458yanb통행료 (IOI18_highway)C++14
0 / 100
5 ms856 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...