Submission #1083305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083305		Math4Life2020	Simurgh (IOI17_simurgh)	C++17	0 / 100	13 ms	9176 KiB

simurgh

// Source: https://usaco.guide/general/io

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

#include "simurgh.h"

using ll = long long; using pii = pair<ll,ll>;

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	ll M = u.size();
	vector<vector<int>> combs = {{-1}};
	for (ll i=0;i<(N-1);i++) {
		vector<vector<int>> combs2;
		for (vector<int> v1: combs) {
			for (ll e=(v1[v1.size()-1]+1);e<M;e++) {
				vector<int> v2 = v1; v2.push_back(e);
				combs2.push_back(v2);
			}
		}
		combs = combs2;
	}
	for (vector<int> v1: combs) {
		vector<int> v0;
		for (ll i=1;i<N;i++) {
			v.push_back(v1[i]);
		}
		ll f[N];
		for (ll i=0;i<N;i++) {
			f[i]=i;
		}
		bool valid = 1;
		for (ll x: v0) {
			ll a = u[x]; ll b=v[x];
			while (a != f[a]) {
				a=f[a];
			}
			while (b != f[b]) {
				b=f[b];
			}
			if (a==b) {
				valid = 0; break;
			} else {
				f[a]=b;
			}
		}
		if (valid) {
			ll a0 = count_common_roads(v0);
			if (a0 == (N-1)) {
				return v0;
			}
		}
	}
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:13:35: warning: control reaches end of non-void function [-Wreturn-type]
   13 |  vector<vector<int>> combs = {{-1}};
      |                                   ^

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