Submission #769758

#	Time	Username	Problem	Language	Result	Execution time	Memory
769758		SanguineChameleon	Highway Tolls (IOI18_highway)	C++17	0 / 100	13 ms	3288 KiB

highway

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

const int maxN = 9e4 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
int distX[maxN];
int distY[maxN];
long long min_dist;
int N, M;

void bfs1(int X, int distX[]) {
	for (int i = 0; i < N; i++) {
		flag[i] = false;
	}
	deque<int> q = {X};
	flag[X] = true;
	distX[X] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (auto e: adj[u]) {
			int v = e.first;
			if (!flag[v]) {
				flag[v] = true;
				distX[v] = distX[u] + 1;
				q.push_back(v);
			}
		}
	}
}

vector<pair<int, int>> bfs2(int X, int distX[], int distY[]) {
	for (int i = 0; i < N; i++) {
		flag[i] = false;
	}
	deque<int> q = {X};
	flag[X] = true;
	vector<pair<int, int>> tree;
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (auto e: adj[u]) {
			int v = e.first;
			int id = e.second;
			if (distX[v] < distY[v] && !flag[v]) {
				flag[v] = true;
				q.push_back(v);
				tree.emplace_back(v, id);
			}
		}
	}
	return tree;
}

int solve(int X, vector<pair<int, int>> treeX, vector<pair<int, int>> treeY) {
	int sz = treeX.size();
	int lt = 0;
	int rt = sz - 1;
	int res = X;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		vector<int> heavy(M, 1);
		for (auto p: treeY) {
			heavy[p.second] = 0;
		}
		for (int i = mt + 1; i < sz; i++) {
			heavy[treeX[i].second] = 0;
		}
		if (ask(heavy) != min_dist) {
			res = treeX[mt].first;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
	N = _N;
	M = U.size();
	for (int i = 0; i < M; i++) {
		adj[U[i]].emplace_back(V[i], i);
		adj[V[i]].emplace_back(U[i], i);
	}
	min_dist = ask(vector<int>(M, 0));
	int lt = 0;
	int rt = M - 1;
	int X = -1;
	int Y = -1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		vector<int> heavy(M);
		for (int i = 0; i <= mt; i++) {
			heavy[i] = 1; 
		}
		if (ask(heavy) != min_dist) {
			X = U[mt];
			Y = V[mt];
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	bfs1(X, distX);
	bfs1(Y, distY);
	vector<pair<int, int>> treeX = bfs2(X, distX, distY);
	vector<pair<int, int>> treeY = bfs2(Y, distY, distX);
	reverse(treeX.begin(), treeX.end());
	reverse(treeY.begin(), treeY.end());
	answer(solve(X, treeX, treeY), solve(Y, treeY, treeX));
}

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