Submission #605093

#	Time	Username	Problem	Language	Result	Execution time	Memory
605093		DanShaders	Highway Tolls (IOI18_highway)	C++17	90 / 100	313 ms	10760 KiB

highway

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

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 9e4 + 10, M = 1.3e5 + 10, INF = 0x3f3f3f3f;

struct Edge {
	int v, i;
};

vector<Edge> g[N];
int dist[N];
int order[N], by_order[N];

void find_pair(int n, vector<int> us, vector<int> vs, int a, int b) {
	int m = sz(us);
	for (int i = 0; i < m; ++i) {
		g[us[i]].push_back({vs[i], i});
		g[vs[i]].push_back({us[i], i});
	}
	int l = 1, r = n;
	ll baseline = ask(vector(m, 0));
	while (r - l > 1) {
		int mid = (l + r) / 2;
		vector w(m, 0);
		for (int i = 0; i < m; ++i) {
			if (max(us[i], vs[i]) >= mid) {
				w[i] = 1;
			}
		}
		if (baseline == ask(w)) {
			r = mid;
		} else {
			l = mid;
		}
	}

	int bound = r;

	queue<int> bfs;
	bfs.push(l);
	int cnt = 0;
	fill(all(dist), +INF);
	dist[l] = 0;
	while (sz(bfs)) {
		int u = bfs.front();
		// cout << u << endl;
		bfs.pop();
		by_order[cnt] = u;
		order[u] = cnt++;
		for (auto [v, _] : g[u]) {
			if (v < bound && dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				bfs.push(v);
			}
		}
	}

	l = 1, r = cnt;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		vector w(m, 0);
		for (int i = 0; i < m; ++i) {
			if (max(us[i], vs[i]) >= bound || max(order[us[i]], order[vs[i]]) >= mid) {
				w[i] = 1;
			}
		}
		if (baseline == ask(w)) {
			r = mid;
		} else {
			l = mid;
		}
	}

	int root = by_order[l];

	// cout << l << " " << r << endl;
	// cout << by_order[0] << " " << by_order[1] << " " << by_order[2] << endl;

	{
		bfs.push(root);
		cnt = 0;
		fill(all(dist), +INF);
		dist[root] = 0;
		while (sz(bfs)) {
			int u = bfs.front();
			bfs.pop();
			by_order[cnt] = u;
			order[u] = cnt++;
			for (auto [v, _] : g[u]) {
				if (dist[v] > dist[u] + 1) {
					dist[v] = dist[u] + 1;
					bfs.push(v);
				}
			}
		}

		l = 0, r = cnt;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			vector w(m, 0);
			for (int i = 0; i < m; ++i) {
				if (max(order[us[i]], order[vs[i]]) >= mid) {
					w[i] = 1;
				}
			}
			if (baseline == ask(w)) {
				r = mid;
			} else {
				l = mid;
			}
		}
		answer(by_order[l], root);
	}	
}

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