Submission #794163

#	Time	Username	Problem	Language	Result	Execution time	Memory
794163		Sohsoh84	Highway Tolls (IOI18_highway)	C++17	51 / 100	153 ms	41644 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
#define all(x)		(x).begin(), (x).end()

const int MAXN = 1e6 + 10;

int from[MAXN], to[MAXN], n, m, par[MAXN];
vector<int> adj[MAXN], dfs_order, fuck;

inline int f(int ind, int v) {
	return from[ind] ^ to[ind] ^ v;
}

void dfs(int v, int p) {
	dfs_order.push_back(v);
	for (int ind : adj[v]) {
		int u = f(ind, v);
		if (u == p) continue;

		par[u] = ind;
		dfs(u, v);
	}
}


inline vector<int> seg(int l, int r) {
	vector<int> ans;
	for (int i = l; i <= r; i++)
		ans.push_back(par[dfs_order[i]]);

	return ans;
}

inline int get(vector<int> vec) {
	vector<int> W(m);
	for (int i = 0; i < m; i++) W[i] = 1;
	for (int e : fuck)
		W[e] = 0;

	for (int e : vec)
		W[e] = 1;

	return ask(W);
}

inline int getp(vector<int> vec) {
	vector<int> W(m);
	for (int i = 0; i < m; i++) 
		W[i] = 1;
	for (int e : vec)
		W[e] = 0;

	return ask(W);
}

inline int get(int l, int r) {
	return get(seg(l, r));
}

inline int find(int root) {
	par[root] = -1;
	dfs_order.clear();

	dfs(root, root);
	int l = 1, r = int(dfs_order.size()) - 1;
	int mx = get(l, r);

	while (l < r) {
		int mid = (l + r) >> 1;	
		if (get(1, mid) == mx) r = mid;
		else l = mid + 1;
	}

	return dfs_order[l];

}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dist[MAXN];

inline vector<int> random_spt() {
	for (int v = 0; v < n; v++)
		shuffle(all(adj[v]), rng);

	vector<int> ans;
	queue<int> q;
	int v = rng() % n;

	memset(dist, 63, sizeof dist);
	q.push(v);
	dist[v] = 0;

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (int ind : adj[v]) {
			int u = f(ind, v);
			if (dist[u] > dist[v] + 1) {
				dist[u] = dist[v] + 1;
				q.push(u);
				ans.push_back(ind);
			}
		}
	}

	return ans;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	m = U.size();
	n = N;

	for (int i = 0; i < m; i++) {
		from[i] = U[i];
		to[i] = V[i];

		adj[from[i]].push_back(i);
		adj[to[i]].push_back(i);
	}

	for (int i = 0; i < m; i++)
		fuck.push_back(i);
	int mn = get({});
	while (true) {
		vector<int> tmp = random_spt();

		if (getp(tmp) == mn) {
			fuck = tmp;
			for (int i = 0; i < n; i++) adj[i].clear();
			for (int ind : tmp) {
				adj[from[ind]].push_back(ind);
				adj[to[ind]].push_back(ind);
			}

			break;
		}
	}

	int v = find(0);
	int u = find(v);

	answer(u, v);
}

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