Submission #390719

#	Time	Username	Problem	Language	Result	Execution time	Memory
390719		JimmyZJX	Highway Tolls (IOI18_highway)	C++14	51 / 100	215 ms	16024 KiB

highway

#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<vector<pair<int, int>>> children(MAXMN);
vector<int> parent(MAXMN);
vector<int> parentEdge(MAXMN);
Vi edgeHeight(MAXMN);
int maxEdgeHeight = 0;
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);
	queue<pair<int, int>> q; q.push({ root, 0 }); // nodeNo, level
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		int x = p.first, level = p.second;
		vis[x] = true;
		for (auto nbP : nbs[x]) {
			if (!vis[nbP.first]) {
				q.push({ nbP.first, level + 1 });
				children[x].push_back({ nbP.first, level + 1 });
				parent[nbP.first] = x; parentEdge[nbP.first] = nbP.second;
				edgeHeight[nbP.second] = level + 1;
				maxEdgeHeight = max(maxEdgeHeight, level + 1);
				edgeSorted.push_back(nbP.second);
			}
		}
	}
}

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 dist = ask(Vi(m)) / A;
	LL maxCost = dist * B;
	// 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 = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1;
		if (ask(ws) == maxCost) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	int leftRank = l;
	int leftEdge = edgeSorted[l];

	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) == maxCost) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	int rightRank = l;
	int rightEdge = edgeSorted[l];

	int rootNode = parentOf(U[leftEdge], V[leftEdge]);
	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;
	}

	LL maxCostL = distL * B + distR * A;

	l = leftRank, r = rightRank;
	while (l < r) {
		int mid = (l + r) / 2;
		Vi ws(m);
		for (int i = leftRank; i <= mid; i++) ws[edgeSorted[i]] = 1;
		for (int e : REdges) ws[e] = 0;
		if (ask(ws) == maxCostL) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	int edgeLeft = edgeSorted[l];
	int leftChild = childOf(U[edgeLeft], V[edgeLeft]);

	answer(leftChild, rightChild);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31