oj.uz

답안 #155172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155172 2019-09-26T18:42:46 Z faremy Simurgh (IOI17_simurgh) C++14
19 / 100
 271 ms 7328 KB 
#include "simurgh.h"
#include <iostream>


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, bool want)
{
	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, true);
		}

		todo.emplace_back(1, 0, edgeToPrev[node]);
		findval(previous[node], stop, expVal, edge, false);
		return (expVal < inTree);
	}
	else
	{
		if (!want)
		{
			findval(find(node), stop, expVal, edge, false);
			return -1;
		}

		int inTree = replace(edgeToPrev[node], edge);
		findval(find(node), stop, expVal, edge, false);
		return (isRoyal[edgeToPrev[node]] ^ (inTree != expVal));
	}
}

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 val = findval(u[iRoad], anc, inTree, iRoad, false);

			int x = todo.size();
			val = std::max(val, findval(v[iRoad], anc, inTree, iRoad, false));

			if (val == -1)
			{
				if (x == 0 && todo.size() != 0 && u[iRoad] != anc)
				{
					int cnt = replace(edgeToPrev[u[iRoad]], iRoad);
					val = isRoyal[edgeToPrev[u[iRoad]]] ^ (cnt != inTree);
				}
				else if (x != 0 && x == todo.size() && v[iRoad] != anc)
				{
					int cnt = replace(edgeToPrev[v[iRoad]], iRoad);
					val = isRoyal[edgeToPrev[v[iRoad]]] ^ (cnt != inTree);
				}
				else
				{
					val = 0;
				}
			}
			
			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;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:233:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     else if (x != 0 && x == todo.size() && v[iRoad] != anc)
                        ~~^~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Incorrect 10 ms 3576 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Incorrect 10 ms 3576 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Incorrect 10 ms 3576 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 157 ms 5384 KB correct
4 Correct 255 ms 7160 KB correct
5 Correct 260 ms 7032 KB correct
6 Correct 233 ms 7160 KB correct
7 Correct 223 ms 7216 KB correct
8 Correct 214 ms 7088 KB correct
9 Correct 254 ms 7328 KB correct
10 Correct 247 ms 7220 KB correct
11 Correct 245 ms 7288 KB correct
12 Correct 250 ms 7276 KB correct
13 Correct 2 ms 380 KB correct
14 Correct 252 ms 7196 KB correct
15 Correct 271 ms 7160 KB correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Incorrect 10 ms 3576 KB WA in grader: NO
5 Halted 0 ms 0 KB -