| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 390815 | JimmyZJX | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 <random>
#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;
Vi edgeRank;
int maxDist;
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;
}
int largestEdgeOfRank(int r) {
forR(i, edgeSorted.size()) {
if (edgeRank[edgeSorted[i]] > r)
return i > 0 ? i - 1 : i;
}
return edgeSorted.size() - 1;
}
void build_tree(int root) {
Vb vis(MAXMN); Vb edgeVis(MAXMN);
edgeSorted.clear(); edgeRank = Vi(MAXMN); maxDist = 0;
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;
maxDist = max(maxDist, level);
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;
}
if (!edgeVis[nbEdge]) {
edgeVis[nbEdge] = true;
edgeSorted.push_back(nbEdge);
edgeRank[nbEdge] = level + 1;
}
}
}
}
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 });
}
for (auto& v : nbs) {
random_shuffle(v.begin(), v.end(), mt19937());
}
build_tree(0);
int far_node = childOf(U[edgeSorted.back()], V[edgeSorted.back()]);
build_tree(far_node);
int far_node2 = childOf(U[edgeSorted.back()], V[edgeSorted.back()]);
Vi DiameterEdges;
for (int n = far_node2; n != far_node; n = parent[n]) {
DiameterEdges.push_back(parentEdge[n]);
}
int midEdge = DiameterEdges[(DiameterEdges.size() - 1) / 2];
int midNode = childOf(U[midEdge], V[midEdge]);
//build_tree(midNode);
build_tree((rand() * 2000) % N);
//build_tree(far_node2);
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 = largestEdgeOfRank(dist);
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 = largestEdgeOfRank(distL - 1), r = min(rightRank, largestEdgeOfRank(distL));
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);
}