Submission #1063447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063447		Tob	Highway Tolls (IOI18_highway)	C++14	51 / 100	185 ms	14740 KiB

highway

#include <bits/stdc++.h>

#include "highway.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int maxN = 90007;

ll odis;
int bio[maxN], dub[maxN];
vector <pii> adj[maxN];

void dfs(int x) {
	bio[x] = 1;
	for (auto y : adj[x]) {
		if (bio[y.F]) continue;
		dub[y.F] = dub[x]+1;
		dfs(y.F);
	}
}

void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
	int m = u.size();
	vector <int> tmp(m, 0);
	odis = ask(tmp);
	for (int i = 0; i < m; i++) {
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	dfs(0);
	
	vector <int> e;
	for (int i = 0; i < m; i++) e.pb(i);
	
	sort(all(e), [&](int x, int y) {return max(dub[u[x]], dub[v[x]]) > max(dub[u[y]], dub[v[y]]);});
	int lo = 0, hi = m-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		vector <int> ed(m, 0);
		for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
		if (odis != ask(ed)) hi = mid;
		else lo = mid+1;
	}
	int nx = u[e[lo]], ny = v[e[lo]];
	
	auto bfs = [&](vector <int> vv) {
		queue <int> q;
		memset(bio, -1, sizeof bio);
		for (auto x : vv) {
			bio[x] = 0;
			q.push(x);
		}
		vector <int> tmp(m, 1);
		while (!q.empty()) {
			int x = q.front(); q.pop();
			for (auto y : adj[x]) {
				if (bio[y.F] != -1) continue;
				bio[y.F] = bio[x] + 1;
				tmp[y.S] = 0;
				q.push(y.F);
			}
		}
		
		vector <int> e;
		for (int i = 0; i < m; i++) e.pb(i);
		sort(all(e), [&](int x, int y){return max(bio[v[x]], bio[u[x]]) < max(bio[v[y]], bio[u[y]]);});
		lo = 0, hi = m-1;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			vector <int> ed; ed = tmp;
			for (int i = 0; i <= mid; i++) ed[e[i]] = 1;
			if (odis/a*b != ask(ed)) lo = mid+1;
			else hi = mid;
		}
		int xx = u[e[lo]];
		if (bio[v[e[lo]]] > bio[xx]) xx = v[e[lo]];
		return xx;
	};
	
	int z = bfs({nx, ny});
	int w = bfs({z});
	
	answer(z, w);
}

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