Submission #832538

#	Time	Username	Problem	Language	Result	Execution time	Memory
832538		MadokaMagicaFan	Simurgh (IOI17_simurgh)	C++14	70 / 100	175 ms	6972 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;
}

const int N = 500;
vector<array<int, 2>> adj[N];

vector<int>
dosp(int n, vector<int> u, vector<int> v) {
	int m = n*(n-1)/2;
	int x, y, z;
	vector<int> edg(n), d(n), r(n-1), ans, t(m, 0);
	vector<array<int, 2>> ak;
	for (int i = 0; i < m; ++i) {
		adj[u[i]].pb({v[i],i});
		adj[v[i]].pb({u[i],i});
	}

	int sp = 0;
	for (int c = 0; c < n; ++c) {
		r.clear();
		for (auto x : adj[c])
			r.pb(x[1]);
		d[c] = count_common_roads(r);
		if (d[c] == 1) sp = c;
	}

	r.clear();
	x = 1;
	if (sp) x = 0;

	for (auto u : adj[x])
		if (u[0] != sp) r.pb(u[1]);

	r.pb(0);
	x = 0; z = 0;
	for (auto u : adj[sp]) {
		r[n-2] = u[1];
		edg[u[0]] = u[1];
		y = count_common_roads(r);
		if (y > x) {
			x = y;
			z = u[1];
		}
	}

	t[z] = 1;
	ans.pb(z);
	r.clear();

	for (int i = 0; i < n; ++i) {
		if (i == sp) continue;
		if (sz(ans) == n-1) break;
		y = d[i];
		r.clear();
		ak.clear();
		z = 0;
		for (auto u : adj[i]) {
			if (t[u[1]]) {
				--y;
				++z;
				r.pb(u[1]);
			} else if (u[0] == sp) {
				r.pb(u[1]);
			} else ak.pb(u);
		}

		if (y == 0) continue;
		int lp = 0; int rp = sz(ak)-1;
		int uz = 0;
		
		while (lp < rp) {
			int m = (lp+rp)/2;
			uz = 0;
			for (int j = 0; j < sz(ak); ++j) {
				if(j < lp || j > m) {
					if (t[edg[ak[j][0]]])
						++uz;
					r.pb(edg[ak[j][0]]);
				}
				else
					r.pb(ak[j][1]);
			}

			int vd = count_common_roads(r);
			if (vd > uz+z)
				rp = m;
			else
				lp = m+1;

			for (int j = 0; j < sz(ak); ++j)
				r.pop_back();
		}

		t[ak[lp][1]] = 1;
		ans.pb(ak[lp][1]);
		if (y > 1) --i;
	}

	return ans;
}

vector<int>
find_roads(int n, vector<int> u, vector<int> v) {
	int m = sz(u);
	if (m == n*(n-1)/2)
		return dosp(n, u, v);
	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] = order[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: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30