제출 #838708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838708		Johann	Simurgh (IOI17_simurgh)	C++14	0 / 100	85 ms	6612 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;
vi U, V;
vvpii adj;
vvi adjmat;
vi deg;
queue<int> todo;
vi goldenTree;
const int NOTHING = 0;
const int FRONTIER = 1;
const int EXPLORED = 2;
vi tmpTree;
int cntQueries;

vi askEdges;

void addEdge(int e)
{
	goldenTree.push_back(e);
	assert(deg[U[e]] > 0 && deg[V[e]] > 0);
	--deg[U[e]], --deg[V[e]];
	if (deg[U[e]] == 1)
		todo.push(U[e]);
	if (deg[V[e]] == 1)
		todo.push(V[e]);
}
void linearSearch(int v, vi &neighbors, vi &candidates)
{
	if (neighbors.empty() || candidates.empty())
		return;
	if (sz(candidates) == 1)
		addEdge(adjmat[v][candidates[0]]);
	else
	{
		tmpTree = vi(all(goldenTree));
		for (int i = 0; i < sz(neighbors) - 1; ++i)
			tmpTree.push_back(adjmat[neighbors[i]][neighbors[i + 1]]);

		vi ans;
		for (int i = 0; i < sz(candidates); ++i)
		{
			int u = candidates[i];
			tmpTree.push_back(adjmat[v][u]);
			ans.push_back(count_common_roads(tmpTree));
			++cntQueries;
			tmpTree.pop_back();
		}
		int maxi = *max_element(all(ans));
		assert(count(all(ans), maxi) == 1);
		for (int i = 0; i < sz(candidates); ++i)
			if (ans[i] == maxi)
			{
				addEdge(adjmat[v][candidates[i]]);
				return;
			}
		assert(false);
	}
}
void findEdge(int v)
{
	vi neighbors;
	for (pii e : adj[v])
		if (deg[e.first] > 0)
			neighbors.push_back(e.first);

	if (sz(neighbors) <= 3)
	{
		linearSearch(v, neighbors, neighbors);
		return;
	}

	tmpTree = vi(all(goldenTree));
	int sq = 2;
	while ((sq + 1) * (sq + 1) < sz(neighbors))
		++sq;

	vvi groups(sq + 1); // groups[sq] is for the rest
	for (int i = 0; i < sq * sq; ++i)
		groups[i % sq].push_back(neighbors[i]);
	for (int i = sq * sq; i < sz(neighbors); ++i)
		groups[sq].push_back(neighbors[i]);

	for (int j = 0; j < sz(groups); ++j)
		for (int i = 0; i < sz(groups[j]) - 1; ++i)
			tmpTree.push_back(adjmat[groups[j][i]][groups[j][i + 1]]);
	if (!groups.back().empty())
		tmpTree.push_back(adjmat[v][groups.back().back()]);

	vi ans;
	for (int j = 0; j < sq; ++j)
	{
		for (int i = 0; i < sq; ++i)
			tmpTree.push_back(adjmat[v][groups[i][j]]);
		ans.push_back(count_common_roads(tmpTree));
		++cntQueries;
		for (int i = 0; i < sq; ++i)
			tmpTree.pop_back();
	}
	int mini = *min_element(all(ans));
	int maxi = *max_element(all(ans));
	vi cand;
	if (maxi != mini)
	{
		assert(count(all(ans), maxi) == 1);
		// search further
		for (int j = 0; j < sq; ++j)
			if (ans[j] == maxi)
			{
				for (int i = 0; i < sq; ++i)
					cand.push_back(groups[i][j]);
				linearSearch(v, neighbors, cand);
				return;
			}
		assert(false);
	}
	else
	{
		// bruteforce groups.back()
		assert(!groups.back().empty());
		linearSearch(v, neighbors, groups.back());
	}
}

std::vector<int> find_roads(int n, std::vector<int> _U, std::vector<int> _V)
{
	N = n;
	U = _U, V = _V;
	adj = vvpii(N);
	adjmat = vvi(N, vi(N, -1));
	for (int i = 0; i < sz(U); ++i)
	{
		adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
		adjmat[U[i]][V[i]] = adjmat[V[i]][U[i]] = i;
	}

	deg.resize(n);
	for (int v = 0; v < n; ++v)
	{
		vi q;
		for (pii e : adj[v])
			q.push_back(e.second);
		deg[v] = count_common_roads(q);
		if (deg[v] == 1)
			todo.push(v);
	}

	goldenTree.clear();

	while (!todo.empty())
	{
		assert(cntQueries <= 12000);
		int v = todo.front();
		todo.pop();
		findEdge(v);
	}

	// cout << cntQueries << endl;
	assert(sz(goldenTree) == N - 1);

	return goldenTree;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30