Submission #1080399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080399		Elias	Simurgh (IOI17_simurgh)	C++17	0 / 100	0 ms	348 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

set<int> trash_edges;

void dfs_spanning(int i, vector<vector<pair<int, int>>> &adj, vector<int> &vis, set<int> &edges)
{
	vis[i] = true;

	for (auto [c, j] : adj[i])
	{
		if (vis[c] || trash_edges.count(j))
			continue;
		edges.insert(j);
		dfs_spanning(c, adj, vis, edges);
	}
}

bool dfs_cycle(int i, int p, vector<vector<pair<int, int>>> &adj, vector<int> &vis, 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))
		{
			assert(!trash_edges.count(j));
			edges.insert(j);
			return true;
		}
	}
	return false;
}

vector<int> U, V;
int N;

int cnt_common_set(set<int> &a)
{
	return count_common_roads(vector(a.begin(), a.end()));
}

vector<vector<pair<int, int>>> build_adj(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;
	vector<vector<pair<int, int>>> adj_all(N);

	for (int i = 0; i < u.size(); i++)
	{
		adj_all[u[i]].push_back({v[i], i});
		adj_all[v[i]].push_back({u[i], i});
	}

	set<int> edges;
	set<int> fancy_edges;

	vector<int> visited(n);

	dfs_spanning(0, adj_all, visited, edges);

	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);

		set<int> cycle_edges;

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

		cycle_edges.erase(i);

		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)
			{
				action_stayed = 1;
				trash_edges.insert(edge);
				break;
			}
			else if (new_count < base_count)
			{
				action_stayed = -1;
				edges.insert(edge);
				fancy_edges.insert(edge);
				trash_edges.insert(i);
				edges.erase(i);
				break;
			}
			else
			{
				stayed.insert(edge);
				edges.insert(edge);
			}
		}

		if (action_stayed == 0)
		{
			trash_edges.insert(i);
			edges.erase(i);
		}
		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);
				edges.erase(edge);
			}
		}

		vector<int> nodes;
		visited = vector<int>(n);
		for (auto edge : edges)
		{
			nodes.push_back(u[edge]);
			nodes.push_back(v[edge]);
			visited[u[edge]] = true;
			visited[v[edge]] = true;
		}

		for (int node : nodes)
		{
			dfs_spanning(node, adj_all, visited, edges);
		}
		base_count = cnt_common_set(edges);
	}

	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)
		wrong_answer();

	return _count_common_roads_internal(r);
}

int main()
{
	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");

	return 0;
}

#endif

Compilation message (stderr)

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

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