Submission #114929

#	Time	Username	Problem	Language	Result	Execution time	Memory
114929		WhipppedCream	Highway Tolls (IOI18_highway)	C++17	90 / 100	987 ms	10220 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;

ll base;

int n, m;

vector< ii > adj[maxn];

int dist[maxn];

void bfs(int s)
{
	for(int i = 0; i< n; i++) dist[i] = 1e9;
	dist[s] = 0;
	queue<int> q; q.push(s);
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(auto kk : adj[u])
		{
			int v = kk.X;
			if(dist[v]> dist[u]+1)
			{
				dist[v] = dist[u]+1;
				q.push(v);
			}
		}
	}
}

bool cmp(int a, int b)
{
	return dist[a]< dist[b];
}

int F(vector<int> &vec)
{
	int lo = 0, hi = n-1;
	while(lo< hi)
	{
		int mid = (lo+hi)/2;
		vector<bool> mark(n, false);
		vector<int> send(m, 1);
		for(int i = 0; i<= mid; i++) mark[vec[i]] = true;
		for(int i = 0; i<= mid; i++)
		{
			int u = vec[i];
			for(auto kk : adj[u])
			{
				int v = kk.X, id = kk.Y;
				if(mark[u] && mark[v])
				{
					send[id] = 0;
				}
			}
		}
		ll exp = ask(send);
		if(exp == base) hi = mid;
		else lo = mid+1;
	}
	return vec[lo];
}

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({V[i], i});
		adj[V[i]].pb({U[i], i});
	}
	base = ask(vector<int>(m, 0));
	vector<int> foo;
	for(int i = 0; i< n; i++) foo.pb(i);
	int v = F(foo);
	bfs(v); sort(foo.begin(), foo.end(), cmp);
	int T = F(foo);
	bfs(T); sort(foo.begin(), foo.end(), cmp);
	int S = F(foo);
	answer(S, T);
}

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