Submission #114868

#	Time	Username	Problem	Language	Result	Execution time	Memory
114868		WhipppedCream	Highway Tolls (IOI18_highway)	C++17	51 / 100	263 ms	25628 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 9e4+5;

vector<ii> adj[maxn];

int ped[maxn];
int dep[maxn];
vector<int> buck[maxn];

int n, m;

void dfs(int u = 0, int p = -1, int d = 0)
{
	dep[u] = d;
	buck[d].pb(u);
	for(auto kk : adj[u])
	{
		int v = kk.X, id = kk.Y;
		if(v == p) continue;
		ped[v] = id;
		dfs(v, u, d+1);
	}
}

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]].pb(ii(V[i], i));
		adj[V[i]].pb(ii(U[i], i));
	}

	ll base = ask(vector<int>(m, 0));
	dfs();
	int down = 0;
	for(int i = 0; i< n; i++) down = max(down, dep[i]);
	int lo = 0, hi = down;
	while(lo< hi)
	{
		int mid = (lo+hi+1)/2;
		vector<int> send(m, 0);
		for(int i = mid; i<= down; i++)
		{
			for(int u : buck[i])
			{
				send[ped[u]] = 1;
			}
		}
		ll exp = ask(send);
		// printf("try %d = %lld\n", mid, exp);
		if(exp == base) hi = mid-1;
		else lo = mid;
	}
	int reach = lo;
	// printf("reach = %d\n", reach);	
	lo = 0, hi = ((int) buck[reach].size())-1;
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		vector<int> send(m, 0);
		for(int i = 0; i<= mid; i++)
		{
			send[ped[buck[reach][i]]] = 1;
		}
		ll exp = ask(send);
		if(exp == base) lo = mid+1;
		else hi = mid;
	}
	int S = buck[reach][lo];
	for(int i = 0; i<= down; i++) buck[i].clear();
	ped[S] = -1;
	dfs(S, -1, 0);
	int reach2 = base/A;
	lo = 0, hi = ((int) buck[reach2].size())-1;
	// for(int i = 0; i< n; i++) printf("ped[%d] = %d\n", i, ped[i]);
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		vector<int> send(m, 0);
		for(int i = 0; i<= mid; i++)
		{
			send[ped[buck[reach2][i]]] = 1;
		}
		ll exp = ask(send);
		if(exp == base) lo = mid+1;
		else hi = mid;
	}
	int T = buck[reach2][lo];
	answer(S, T);
}

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