Submission #390721

#TimeUsernameProblemLanguageResultExecution timeMemory
390721JimmyZJX통행료 (IOI18_highway)C++14
90 / 100
313 ms12076 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> #include "highway.h" using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) #define MAXMN 130003 vector<vector<pair<int, int>>> nbs(MAXMN); // {nb, edgeNo} vector<int> parent(MAXMN); vector<int> parentEdge(MAXMN); Vi edgeSorted; int parentOf(int n1, int n2) { if (parent[n1] == n2) return n2; return n1; } int childOf(int n1, int n2) { if (parent[n1] == n2) return n1; return n2; } void build_tree(int root) { Vb vis(MAXMN); Vb edgeVis(MAXMN); edgeSorted.clear(); queue<pair<int, int>> q; q.push({ root, 0 }); // nodeNo, level vis[root] = true; while (!q.empty()) { auto p = q.front(); q.pop(); int x = p.first, level = p.second; for (auto nbP : nbs[x]) { int nb = nbP.first, nbEdge = nbP.second; if (!vis[nb]) { vis[nb] = true; q.push({ nb, level + 1 }); parent[nb] = x; parentEdge[nb] = nbEdge; edgeSorted.push_back(nbEdge); edgeVis[nbEdge] = true; } else if (!edgeVis[nbEdge]) { edgeSorted.push_back(nbEdge); edgeVis[nbEdge] = true; } } } } void find_pair(int N, Vi U, Vi V, int A, int B) { int m = U.size(); forR(i, m) { nbs[U[i]].push_back({ V[i], i }); nbs[V[i]].push_back({ U[i], i }); } build_tree(0); LL minCost = ask(Vi(m)); LL dist = minCost / A; // search for range of edges int l = 0, r = m - 1; while (l < r) { int mid = (l + r) / 2; Vi ws(m); for (int i = 0; i <= mid; i++) ws[edgeSorted[i]] = 1; if (ask(ws) == minCost) { l = mid + 1; } else { r = mid; } } int leftEdge = edgeSorted[l]; int rootNode = parentOf(U[leftEdge], V[leftEdge]); build_tree(rootNode); l = 0, r = m - 1; while (l < r) { int mid = (l + r) / 2; Vi ws(m); for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1; if (ask(ws) == minCost) { r = mid; } else { l = mid + 1; } } int rightRank = l; int rightEdge = edgeSorted[l]; int rightChild = childOf(U[rightEdge], V[rightEdge]); LL distR = 0; Vi REdges; for (int n = rightChild; n != rootNode; n = parent[n]) { REdges.push_back(parentEdge[n]); distR++; } LL distL = dist - distR; if (distL == 0) { answer(rootNode, rightChild); return; } l = 0, r = rightRank; while (l < r) { int mid = (l + r) / 2; Vi ws(m); for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1; for (int e : REdges) ws[e] = 0; if (ask(ws) == minCost) { r = mid; } else { l = mid + 1; } } int edgeLeft = edgeSorted[l]; int leftChild = childOf(U[edgeLeft], V[edgeLeft]); answer(leftChild, rightChild); }
#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...