제출 #390721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390721		JimmyZJX	통행료 (IOI18_highway)	C++14	90 / 100	313 ms	12076 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<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);
}

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