Submission #1241723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241723		SpyrosAliv	Simurgh (IOI17_simurgh)	C++20	13 / 100	3093 ms	328 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> u, v;
int n, m;
bool found = false;
vector<int> curr;
const int MN = 51;
int par[MN], sz[MN];

int find(int u) {
	if (par[u] == u) return u;
	return par[u] = find(par[u]);
}

void merge(int u, int v) {
	if (u == v) return;
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
}

bool good(vector<int> av) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		sz[i] = 1;
	}
	for (auto x: av) {
		if (find(u[x]) == find(v[x])) return false;
		merge(u[x], v[x]);
	}
	return count_common_roads(av) == n-1;
}

void brute(int nxt = 0) {
	if (curr.size() == n-1) {
		if (good(curr)) {
			found = true;
		}
		return;
	}
	if (nxt >= m) return;
	curr.push_back(nxt);
	brute(nxt+1);
	if (found) return;
	curr.pop_back();
	brute(nxt+1);
	return;
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	u = U;
	v = V;
	n = N;
	m = u.size();
	brute();
	return curr;
}

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