제출 #710541

#제출 시각아이디문제언어결과실행 시간메모리
710541Cyanmond통행료 (IOI18_highway)C++17
6 / 100
125 ms14436 KiB
#include "highway.h" #include <bits/stdc++.h> using i64 = long long; void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) { const int M = (int)U.size(); std::vector<std::vector<std::pair<int, int>>> graph(N); for (int i = 0; i < M; ++i) { graph[U[i]].push_back({V[i], i}); graph[V[i]].push_back({U[i], i}); } // find one of the vertices on the min cost path const int distLen = ask(std::vector<int>(M, 0)) / A; auto binarySearch = [&](int ng, int ok, auto &&f) { while (std::abs(ok - ng) > 1) { const auto mid = (ok + ng) / 2; if (f(mid)) ok = mid; else ng = mid; } return ok; }; int root = binarySearch(0, N, [&](const int m) { std::vector<int> w(M); for (int i = 0; i < M; ++i) { const int mn = std::min(U[i], V[i]); w[i] = mn < m ? 0 : 1; } return ask(w) == (i64)(distLen) * A; }) - 1; // construct BFS-Tree std::vector<std::vector<std::pair<int, int>>> bfsTree(N); std::queue<int> que; que.push(root); std::vector<bool> isSeen(N); isSeen[root] = true; std::vector<bool> exTree(M); while (not que.empty()) { const int f = que.front(); que.pop(); for (const auto &[t, i] : graph[f]) { if (isSeen[t]) continue; isSeen[t] = true; bfsTree[f].push_back({t, i}); exTree[i] = true; que.push(t); } } // Euler-Tour std::vector<int> in(N, -1), revIn(N); auto dfs = [&](auto &&self, const int v, int &id) -> void { revIn[id] = v; in[v] = id; ++id; for (const auto &[t, i] : bfsTree[v]) { if (in[t] != -1) continue; self(self, t, id); } }; int gomi = 0; dfs(dfs, root, gomi); // binary search, find path // find r int r = binarySearch(0, N, [&](const int m) { std::vector<int> w(M); for (int i = 0; i < M; ++i) { if (not exTree[i]) continue; const int mx = std::max(in[U[i]], in[V[i]]); w[i] = mx < m ? 0 : 1; } return ask(w) == (i64)(distLen) * A; }) - 1; int l = binarySearch(0, std::max(r, 1), [&](const int m) { std::vector<int> w(M); for (int i = 0; i < M; ++i) { if (not exTree[i]) continue; const int mx = std::max(in[U[i]], in[V[i]]); if (mx >= r) w[i] = 0; else w[i] = mx < m ? 0 : 1; } return ask(w) == (i64)(distLen) * A; }) - 1; answer(revIn[l], revIn[r]); }
#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...