제출 #289387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289387		dolphingarlic	통행료 (IOI18_highway)	C++14	100 / 100	302 ms	10972 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> graph[90000], ord[2];
bool visited[90000];
int ans[2];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = int(U.size());
	for (int i = 0; i < M; i++) {
		graph[U[i]].push_back({V[i], i});
		graph[V[i]].push_back({U[i], i});
	}

	vector<int> W(M, 0);
	long long path_len = ask(W) / A;

	int l = 0, r = M - 1;
	while (l != r) {
		int mid = (l + r) / 2;
		fill(W.begin(), W.end(), 0);
		for (int i = 0; i <= mid; i++) W[i] = 1;
		long long res = ask(W);
		if (res == path_len * A) l = mid + 1;
		else r = mid;
	}
	int m_edge = l, uu = U[l], vv = V[l];

	visited[uu] = visited[vv] = true;
	queue<pair<int, int>> q;
	q.push({uu, 0}); q.push({vv, 1});
	ord[0].push_back({uu, -1}); ord[1].push_back({vv, -1});
	while (q.size()) {
		int curr, sub;
		tie(curr, sub) = q.front();
		q.pop();
		for (pair<int, int> i : graph[curr]) {
			if (!visited[i.first] && i.second > m_edge) {
				visited[i.first] = true;
				ord[sub].push_back(i);
				q.push({i.first, sub});
			}
		}
	}

	for (int s = 0; s < 2; s++) {
		l = 0, r = ord[s].size() - 1;
		while (l != r) {
			int mid = (l + r) / 2;
			fill(W.begin(), W.end(), 1);
			W[m_edge] = 0;
			for (pair<int, int> i : ord[1 - s]) if (i.second != -1) W[i.second] = 0;
			for (int i = 1; i <= mid; i++) W[ord[s][i].second] = 0;
			long long dist = ask(W);
			if (dist == path_len * A) r = mid;
			else l = mid + 1;
		}
		ans[s] = ord[s][l].first;
	}

	answer(ans[0], ans[1]);
}

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