Submission #295124

#	Time	Username	Problem	Language	Result	Execution time	Memory
295124		Kastanda	Highway Tolls (IOI18_highway)	C++11	90 / 100	1114 ms	13208 KiB

highway

// M
#include<bits/stdc++.h>
#include "highway.h"
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 90004, TOF = 31000;
int n, m, ca, cb, dist, root, H[N];
ll MnCost;
vector < int > alwaysMarked;
vector < pair < int , int > > Adj[N];
inline ll Ask(vector < int > vec)
{
	vector < int > TMp(m, 0);
	for (int i : vec)
		TMp[i] = 1;
	return ask(TMp);
}
inline bool HasImpact(vector < int > vec)
{
	return (Ask(vec) > MnCost);
}
inline vector < int > MarkAll(vector < int > vec)
{
	vector < int > TMp(m, 0), ret;
	for (int i : vec)
		for (auto e : Adj[i])
			TMp[e.second] = 1;
	for (int i : alwaysMarked)
		for (auto e : Adj[i])
			TMp[e.second] = 1;
	for (int i = 0; i < m; i ++)
		if (TMp[i])
			ret.pb(i);
	return ret;
}

void find_pair(int _n, vector < int > _U, vector < int > _V, int _A, int _B)
{
	n = _n;
	m = (int)_U.size();
	for (int i = 0; i < m; i ++)
	{
		Adj[_U[i]].pb({_V[i], i});
		Adj[_V[i]].pb({_U[i], i});
	}
	ca = _A; cb = _B;

	MnCost = Ask(vector < int > {});
	dist = MnCost / ca;

	auto GenerateVec = [](int l, int r){
		vector < int > vec;
		for (int i = l; i < r; i ++)
			vec.pb(i);
		return vec;
	};

	int le = 0, ri = n, md;
	if (n > TOF * 2 && HasImpact(MarkAll(GenerateVec(0, TOF))))
		le = 0, ri = TOF;
	else if (n > TOF * 2)
		alwaysMarked = GenerateVec(0, TOF), le = TOF, ri = n;
	while (ri - le > 1)
	{
		md = (le + ri) >> 1;
		if (HasImpact(MarkAll(GenerateVec(0, md))))
			ri = md;
		else
			le = md;
	}
	alwaysMarked = GenerateVec(0, le);
	root = le;
	queue < int > qu;
	memset(H, -1, sizeof(H));
	H[root] = 0; qu.push(root);
	while (qu.size())
	{
		int v = qu.front();
		qu.pop();
		for (auto u : Adj[v])
			if (u.first >= le && H[u.first] == -1)
				H[u.first] = H[v] + 1, qu.push(u.first);
	}

	vector < int > Rs;
	vector < int > marked(n, 0);
	for (int i : alwaysMarked)
		marked[i] = 1;
	for (int w = 0; w < 2; w ++)
	{
		vector < int > srt;
		for (int i = 0; i < n; i ++)
			if (marked[i] == 0)
				srt.pb(i);
		sort(srt.begin(), srt.end(), [&](int i, int j){return H[i] > H[j];});

		auto GenVec = [&](int l, int r){
			assert(r <= (int)srt.size());
			vector < int > vec;
			for (int i = l; i < r; i ++)
				vec.pb(srt[i]);
			return vec;
		};

		le = 0, ri = (int)srt.size();
		if (srt.size() > TOF * 2 && HasImpact(MarkAll(GenVec(0, TOF))))
			le = 0, ri = TOF;
		else if (srt.size() > TOF * 2)
		{
			for (int i = 0; i < TOF; i ++)
				alwaysMarked.pb(srt[i]);
			le = TOF;
		}

		while (ri - le > 1)
		{
			md = (le + ri) >> 1;
			if (HasImpact(MarkAll(GenVec(0, md))))
				ri = md;
			else
				le = md;
		}

		Rs.pb(srt[le]);
		qu.push(srt[le]);
		marked[srt[le]] = 1;
		while (qu.size())
		{
			int v = qu.front();
			qu.pop();
			for (auto u : Adj[v])
				if (!marked[u.first] && u.first != root && H[u.first] == H[v] - 1)
					marked[u.first] = 1, qu.push(u.first);
		}
	}
	assert((int)Rs.size() == 2);
	answer(Rs[0], Rs[1]);
	return ;

}

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