Submission #155180

#	Time	Username	Problem	Language	Result	Execution time	Memory
155180		faremy	Simurgh (IOI17_simurgh)	C++14	100 / 100	260 ms	7244 KiB

simurgh

#include "simurgh.h"
#include <algorithm>


struct Edge
{
	Edge(int u, int v, int i) : start(u), end(v), id(i) {}
	int start, end, id;
};

const int MAXN = 500;
const int MAXM = MAXN * (MAXN - 1) / 2;
const int LOGN = 9;

std::vector<Edge> graph[MAXN];
int parent[MAXN];

int posInSpanning[MAXM];
std::vector<Edge> spanning;

int previous[MAXN], edgeToPrev[MAXN];
int depth[MAXN];
int ancester[MAXN][LOGN];

std::vector<int> golden;
std::vector<Edge> todo;

std::vector<int> order;
bool seen[MAXN];

bool isRoyal[MAXM];
std::vector<int> royal;

void disjointreset(int nodes)
{
	for (int iNode = 0; iNode < nodes; iNode++)
		parent[iNode] = iNode;
}

int find(int node)
{
	if (node != parent[node])
		parent[node] = find(parent[node]);
	return parent[node];
}

bool merge(int start, int end)
{
	int st = find(start), nd = find(end);
	parent[nd] = st;
	return (st != nd);
}

void root(int node)
{
	for (Edge &edge : graph[node])
		if (posInSpanning[edge.id] != -1 && previous[node] != edge.end)
		{
			depth[edge.end] = depth[node] + 1;
			previous[edge.end] = node;
			edgeToPrev[edge.end] = edge.id;
			isRoyal[edge.id] = true;
			root(edge.end);
		}

	order.emplace_back(node);
}

void setbinlift(int nodes)
{
	for (int iNode = 0; iNode < nodes; iNode++)
	{
		ancester[iNode][0] = previous[iNode];
		for (int iExp = 1; iExp < LOGN; iExp++)
			ancester[iNode][iExp] = -1;
	}
}

int findanc(int node, int exp)
{
	if (ancester[node][exp] == -1)
		ancester[node][exp] = findanc(findanc(node, exp - 1), exp - 1);
	return ancester[node][exp];
}

int lift(int node, int dist)
{
	if (dist == 0)
		return node;
	int exp = 31 - __builtin_clz(dist);
	return lift(findanc(node, exp), dist - (1 << exp));
}

int lca(int u, int v)
{
	if (depth[u] < depth[v])
		std::swap(u, v);
	u = lift(u, depth[u] - depth[v]);

	if (u == v)
		return u;
	for (int iExp = LOGN - 1; iExp > -1; iExp--)
		if (findanc(u, iExp) != findanc(v, iExp))
		{
			u = findanc(u, iExp);
			v = findanc(v, iExp);
		}

	return findanc(u, 0);
}

int replace(int edge, int other)
{
	golden[posInSpanning[edge]] = other;
	int inTree = count_common_roads(golden);
	golden[posInSpanning[edge]] = edge;
	return inTree;
}

int findval(int node, int stop, int expVal, int edge, int &known)
{
	if (depth[node] <= depth[stop])
		return -1;
	if (find(node) == node)
	{
		int inTree = replace(edgeToPrev[node], edge);
		parent[node] = previous[node];
		
		if (inTree == expVal)
		{
			todo.emplace_back(0, 0, edgeToPrev[node]);
			return findval(previous[node], stop, expVal, edge, known);
		}

		todo.emplace_back(1, 0, edgeToPrev[node]);
		findval(previous[node], stop, expVal, edge, known);
		return (expVal < inTree);
	}
	else
	{
		known = edgeToPrev[node];
		return findval(find(node), stop, expVal, edge, known);
	}
}

int count(int node, std::vector<int> &edges, int nodes)
{
	disjointreset(nodes);
	golden.clear();

	for (int edge : edges)
	{
		merge(graph[node][edge].start, graph[node][edge].end);
		golden.emplace_back(graph[node][edge].id);
	}

	int inTree = 0;
	for (Edge &edge : spanning)
		if (merge(edge.start, edge.end))
		{
			inTree += isRoyal[edge.id];
			golden.emplace_back(edge.id);
		}

	return (count_common_roads(golden) - inTree);
}

int search(int left, int right, std::vector<int> &sspace, int node, int nodes)
{
	if (right - left == 1)
		return left;
	std::vector<int> ask;

	for (int iEdge = left; iEdge < (left + right) / 2; iEdge++)
		ask.emplace_back(sspace[iEdge]);
	if (count(node, ask, nodes) > 0)
		return search(left, (left + right) / 2, sspace, node, nodes);
	return search((left + right) / 2, right, sspace, node, nodes);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
	int roads = u.size();
	for (int iRoad = 0; iRoad < roads; iRoad++)
	{
		graph[u[iRoad]].emplace_back(u[iRoad], v[iRoad], iRoad);
		graph[v[iRoad]].emplace_back(v[iRoad], u[iRoad], iRoad);
	}

	disjointreset(n);
	for (int iRoad = 0; iRoad < roads; iRoad++)
	{
		if (merge(u[iRoad], v[iRoad]))
		{
			posInSpanning[iRoad] = spanning.size();
			spanning.emplace_back(u[iRoad], v[iRoad], iRoad);
			golden.emplace_back(iRoad);
		}
		else
		{
			posInSpanning[iRoad] = -1;
		}
	}

	int inTree = count_common_roads(golden);
	root(0);
	setbinlift(n);
	
	disjointreset(n);
	for (int iRoad = 0; iRoad < roads; iRoad++)
		if (posInSpanning[iRoad] == -1)
		{
			int anc = lca(u[iRoad], v[iRoad]);
			int known = -1;
			int val = std::max(findval(u[iRoad], anc, inTree, iRoad, known), findval(v[iRoad], anc, inTree, iRoad, known));

			if (val == -1 && !todo.empty())
			{
				if (known == -1)
					val = 0;
				else
					val = isRoyal[known] ^ (replace(known, iRoad) != inTree);
			}
			
			while (!todo.empty())
			{
				isRoyal[todo.back().id] = val ^ (todo.back().start);
				todo.pop_back();
			}
		}
	
	for (int iNode = 0; iNode < n; iNode++)
	{
		std::vector<int> searchspace;
		for (int iEdge = 0; iEdge < (int)graph[order[iNode]].size(); iEdge++)
			if (seen[graph[order[iNode]][iEdge].end] && posInSpanning[graph[order[iNode]][iEdge].id] == -1)
				searchspace.emplace_back(iEdge);

		int connected = count(order[iNode], searchspace, n);
		for (int iRoy = 0; iRoy < connected; iRoy++)
		{
			int pos = search(0, searchspace.size(), searchspace, order[iNode], n);
			isRoyal[graph[order[iNode]][searchspace[pos]].id] = true;
			searchspace.erase(searchspace.begin() + pos);
		}

		seen[order[iNode]] = true;
	}

	for (int iEdge = 0; iEdge < roads; iEdge++)
		if (isRoyal[iEdge])
			royal.emplace_back(iEdge);
	return royal;
}

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