Submission #139139

#	Time	Username	Problem	Language	Result	Execution time	Memory
139139		random0029	Highway Tolls (IOI18_highway)	C++14	18 / 100	345 ms	18704 KiB

highway

// ItnoE
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
const int N = 100005, MXN = N * 2;
int n, m, ts, X, Y, H[N], Mark[N], V[MXN], U[MXN];
ll ndist, dist;
vector < int > Q, Adj[N];
inline void BFS(int root)
{
	memset(H, -1, sizeof(H));
	H[root] = 0;
	queue < int > qu;
	qu.push(root);
	while (qu.size())
	{
		int v = qu.front();
		qu.pop();
		for (int id : Adj[v])
		{
			int u = V[id] ^ U[id] ^ v;
			if (H[u] == -1)
				H[u] = H[v] + 1, qu.push(u);
		}
	}
}
inline int GetHeight()
{
	int Mxh = 0;
	for (int i = 0; i < n; i ++)
		Mxh = max(Mxh, H[i]);
	int le = 1, ri = Mxh + 1, md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = 0; i < m; i ++)
			Q[i] = 0;
		for (int i = 0; i < n; i ++)
			if (H[i] >= md)
				for (int id : Adj[i])
				{
					int u = V[id] ^ U[id] ^ i;
					if (H[u] < H[i])
						Q[id] = 1;
				}
		ll dd = ask(Q);
		if (dd == dist)
			ri = md;
		else
			le = md;
	}
	return (le);
}
inline int FindS(int h)
{
	ts ++;
	vector < int > vec;
	for (int i = 0; i < n; i ++)
		if (H[i] == h && (ts == 1 || Mark[i] == 1))
			vec.push_back(i);
	int le = 0, ri = (int)vec.size(), md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = 0; i < m; i ++)
			Q[i] = 0;
		for (int i = le; i < md; i ++)
			for (int id : Adj[vec[i]])
			{
				int u = V[id] ^ U[id] ^ vec[i];
				if (H[u] < H[vec[i]])
					Q[id] = 1;
			}
		ll dd = ask(Q);
		if (dd == dist)
			le = md;
		else
			ri = md;
	}
	return (vec[le]);
}
void find_pair(int _n, vector < int > _V, vector < int > _U, int _X, int _Y)
{
	n = _n;
	m = (int)_V.size();
	X = _X; Y = _Y;
	for (int i = 0; i < m; i ++)
	{
		V[i] = _V[i]; U[i] = _U[i];
		Adj[V[i]].push_back(i);
		Adj[U[i]].push_back(i);
	}
	Q = vector < int > (m, 0);
	dist = ask(Q);
	ndist = dist / X;
	int le = 0, ri = n, md;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		for (int i = le; i < md; i ++)
			for (int id : Adj[i])
				Q[id] = 1;
		ll dd = ask(Q);
		for (int i = le; i < md; i ++)
			for (int id : Adj[i])
				Q[id] = 0;
		if (dist == dd)
			le = md;
		else
		{
			for (int i = le; i < md; i ++)
				for (int id : Adj[i])
					Q[id] = 0;
			ri = md;
		}
	}
	int root = le;
	{
		for (int id : Adj[root])
			Q[id] = 1;
		ll dd = ask(Q);
		if (dd == dist)
			assert(0);
	}
	BFS(root);
	int hs = GetHeight();
	int ht = ndist - hs;
	for (int i = 0; i < n; i ++)
		if (H[i] == ht)
			Mark[i] = 1;
	int s = FindS(hs);
	BFS(s);
	int t = FindS(ndist);
	answer(s, t);
}

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