제출 #414989

#제출 시각아이디문제언어결과실행 시간메모리
414989SuhaibSawalha1통행료 (IOI18_highway)C++17
18 / 100
293 ms8312 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; vector<vector<array<int, 2>>> adj; vector<array<int, 2>> to_ask; int n, m, dp, A, B; void dfs (int u = 0, int p = -1, int d = 1) { for (auto &v : adj[u]) { if (v[0] ^ p) { if (d == dp) { vector<int> ak(m, 0); ak[v[1]] = 1; to_ask.push_back(v); } else { dfs(v[0], u, d + 1); } } } } void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { n = N; m = U.size(); ::A = A; ::B = B; adj.assign(n, {}); bool subtask3 = 1; for (int i = 0; i < m; ++i) { adj[U[i]].push_back({V[i], i}); adj[V[i]].push_back({U[i], i}); subtask3 &= U[i] == i && V[i] == i + 1; } dp = ask(vector<int>(m, 0)) / A; if (subtask3) { int l = 0, r = m - 1; while (l < r) { int mid = (l + r + 1) / 2; vector<int> ak(m, 1); fill(ak.begin(), ak.begin() + mid, 0); if (ask(ak) == B * 1LL * dp) { l = mid; } else { r = mid - 1; } } return answer(l, l + dp); } dfs(); int l = 0, r = to_ask.size() - 1; while (l < r) { int mid = (l + r) / 2; vector<int> ak(m, 0); for (int i = 0; i <= mid; ++i) { ak[to_ask[i][1]] = 1; } if (ask(ak) != dp * 1LL * A) { r = mid; } else { l = mid + 1; } } answer(0, to_ask[l][0]); }
#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...