Submission #1080558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080558		Elias	Simurgh (IOI17_simurgh)	C++17	51 / 100	637 ms	3164 KiB

simurgh

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#ifdef _DEBUG
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v);
int count_common_roads(const std::vector<int> &r);
#else
#include "simurgh.h"
#endif

vector<int> U, V;
int N;

unordered_set<int> trash_edges;

vector<int> par;

int find_parent(int a)
{
	if (par[a] == a)
		return a;
	return par[a] = find_parent(par[a]);
}

bool unite(int a, int b)
{
	if (rand() % 2)
		swap(a, b);

	a = find_parent(a), b = find_parent(b);
	if (a == b)
		return false;
	par[b] = a;
	return true;
}

void reset_parent()
{
	par = vector<int>(N);
	for (int i = 0; i < N; i++)
		par[i] = i;
}

void dfs_spanning(unordered_set<int> &edges)
{
}

bool dfs_cycle(int i, int p, vector<vector<pair<int, int>>> &adj, vector<int> &vis, unordered_set<int> &edges)
{
	vis[i] = true;

	for (auto [c, j] : adj[i])
	{
		if (c == p)
			continue;
		if (vis[c] || dfs_cycle(c, i, adj, vis, edges))
		{
			edges.insert(j);
			return true;
		}
	}
	return false;
}

int cnt_common_set(unordered_set<int> &a)
{
	// if (results.count(a))
	// 	return results[a];
	return count_common_roads(vector(a.begin(), a.end()));
}

vector<vector<pair<int, int>>> build_adj(unordered_set<int> &edges)
{
	vector<vector<pair<int, int>>> adj(N);
	for (int i : edges)
	{
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}
	return adj;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
	U = u, V = v;
	N = n;

	unordered_set<int> edges;
	unordered_set<int> fancy_edges;

	vector<int> visited(n);

	reset_parent();
	for (int i = 0; i < U.size(); i++)
	{
		if (unite(U[i], V[i]))
			edges.insert(i);
	}

	int base_count = cnt_common_set(edges);

	for (int i = 0; i < u.size(); i++)
	{
		if (edges.count(i) || fancy_edges.count(i) || trash_edges.count(i))
			continue;

		edges.insert(i);

		auto adj = build_adj(edges);
		visited = vector<int>(n);

		unordered_set<int> cycle_edges;

		dfs_cycle(u[i], -1, adj, visited, cycle_edges);

		cycle_edges.erase(i);

		unordered_set<int> stayed;
		int action_stayed = 0;

		for (int edge : cycle_edges)
		{
			if (fancy_edges.count(edge))
				continue;

			edges.erase(edge);

			int new_count = cnt_common_set(edges);

			if (new_count > base_count)
			{ // better than other edge
				trash_edges.insert(edge);

				fancy_edges.insert(i);
				edges.insert(i);
				action_stayed = 1;

				base_count = new_count;
				break;
			}
			else if (new_count < base_count)
			{
				trash_edges.insert(i);
				edges.erase(i);
				action_stayed = -1;

				edges.insert(edge);
				fancy_edges.insert(edge);
				break;
			}
			else
			{
				if (trash_edges.count(edge))
				{
					trash_edges.insert(i);
					edges.insert(i);

					action_stayed = -1;
					break;
				}
				else
				{
					edges.insert(edge);
					stayed.insert(edge);
				}
			}
		}

		if (action_stayed == 0)
		{
			trash_edges.insert(i);
			edges.erase(i);
			for (int edge : stayed)
				trash_edges.insert(edge);
		}
		else if (action_stayed == 1)
		{
			for (int edge : stayed)
				fancy_edges.insert(edge);
		}
		else if (action_stayed == -1)
		{
			for (int edge : stayed)
				trash_edges.insert(edge);
		}
	}

	for (auto edge : edges)
		fancy_edges.insert(edge);

	return vector(fancy_edges.begin(), fancy_edges.end());
}

#ifdef _DEBUG

using namespace std;

static int MAXQ = 30000;

static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;
static vector<int> parent;

static int find(int node)
{
	return (parent[node] == node ? node : parent[node] = find(parent[node]));
}

static bool merge(int v1, int v2)
{
	v1 = find(v1);
	v2 = find(v2);
	if (v1 == v2)
		return false;
	parent[v1] = v2;
	return true;
}

static void wrong_answer()
{
	printf("NO\n");
	exit(0);
}

static bool is_valid(const vector<int> &r)
{
	if (int(r.size()) != n - 1)
		return false;

	for (int i = 0; i < n - 1; i++)
		if (r[i] < 0 || r[i] >= m)
			return false;

	parent.resize(n);
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
	}
	for (int i = 0; i < n - 1; i++)
	{
		if (!merge(u[r[i]], v[r[i]]))
		{
			return false;
		}
	}
	return true;
}

static int _count_common_roads_internal(const vector<int> &r)
{
	if (!is_valid(r))
		wrong_answer();

	int common = 0;
	for (int i = 0; i < n - 1; i++)
	{
		bool is_common = goal[r[i]];
		if (is_common)
			common++;
	}

	return common;
}

int count_common_roads(const vector<int> &r)
{
	q++;
	if (q > MAXQ)
	{
		cout << "Too many queries!!!\n";
		wrong_answer();
	}

	return _count_common_roads_internal(r);
}

int main()
{
	// cin.tie(0);
	// ios_base::sync_with_stdio(false);

	freopen("/home/elias/Downloads/ioi2017tests/simurgh/tests/3-01.in", "r", stdin);

	string trash;
	cin >> trash;

	assert(2 == scanf("%d %d", &n, &m));
	assert(1 == scanf("%d", &MAXQ));

	u.resize(m);
	v.resize(m);

	for (int i = 0; i < m; i++)
		assert(2 == scanf("%d %d", &u[i], &v[i]));

	goal.resize(m, false);

	for (int i = 0; i < n - 1; i++)
	{
		int id;
		assert(1 == scanf("%d", &id));
		goal[id] = true;
	}

	vector<int> result = find_roads(n, u, v);

	if (_count_common_roads_internal(result) != n - 1)
		wrong_answer();

	printf("OK\n");
	for (int i = 0; i < (int)result.size(); i++)
	{
		if (i)
			printf(" ");
		printf("%d", result[i]);
	}
	printf("\n");

	cout << q << "\n";

	return 0;
}

#endif

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < U.size(); i++)
      |                  ~~^~~~~~~~~~
simurgh.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~

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