Submission #832488

#	Time	Username	Problem	Language	Result	Execution time	Memory
832488		MadokaMagicaFan	Simurgh (IOI17_simurgh)	C++14	0 / 100	0 ms	212 KiB

simurgh

#include "bits/stdc++.h"
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int p[500];
int getp(int x) { return p[x] = (x == p[x] ? x : getp(p[x])); }
int uni(int a, int b) {
	a = getp(a);
	b = getp(b);
	if (a == b) return 0;
	p[a] = b;
	return 1;
}

vector<int>
find_roads(int n, vector<int> u, vector<int> v) {
	int m = sz(u);
	vector<int> ans, r, us(m, 0), z, order(m);
	iota(order.begin(), order.end(), 0);
	shuffle(order.begin(), order.end(), rng);
	for (int i = 0; i < n-1; ++i) {
		for (int i = 0; i < n; ++i) p[i] = i;
		int c = 0;
		shuffle(order.begin(), order.end(), rng);
		if (sz(ans) == n-1) break;
		r = ans;
		for (auto x : ans) {
			c += uni(u[x], v[x]);
		}

		int p = 0;
		while (c < n-2) {
			if (uni(u[order[p]], v[order[p]])) {
				++c;
				r.pb(order[p]);
			}
			++p;
		}

		while (us[order[p]] || getp(u[order[p]]) == getp(v[order[p]]))
			++p;
		r.pb(order[p]);
		z.clear();
		z.pb(order[p]);
		assert(sz(r) == n-1);
		int x = count_common_roads(r);

		for (int j = p+1; j < m; ++j) {
			if(us[order[j]]) continue;
			if (getp(u[order[j]]) == getp(v[order[j]])) continue;
			r[n-2] = j;
			us[order[j]] = 1;
			int l = count_common_roads(r);
			if (l == x) {
				z.pb(order[j]);
			} else if (l < x) {
				break;
			} else if (l > x) {
				z.clear(); z.pb(order[j]);
				break;
			}
		}

		for (auto j : z)
			ans.pb(j);
	}

	return ans;
}

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