Submission #72677

#	Time	Username	Problem	Language	Result	Execution time	Memory
72677		mhnd	Simurgh (IOI17_simurgh)	C++14	13 / 100	35 ms	544 KiB

simurgh

#include "simurgh.h"
using namespace std;
const int MAX = 7;
int par[MAX];
int find(int v)
{
	return (par[v] == v ? v : par[v] = find(par[v]));
}
bool merge(int u, int v)
{
	u = find(u);
	v = find(v);
	if (u == v)
		return false;
	par[u] = v;
	return true;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = v.size();
	for (int mask = 0; mask < (1 << m); mask++)
		if (__builtin_popcount(mask) == n - 1)
		{
			for (int i = 0; i < n; i++)
				par[i] = i;
			bool valid = true;
			vector<int> edges;
			for (int i = 0; i < m; i++)
				if ((1 << i) & mask)
				{
					edges.push_back(i);
					valid &= merge(u[i], v[i]);
				}
			if (valid && count_common_roads(edges) == n-1)
				return edges;
		}
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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