Submission #1210525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210525		Mousa_Aboubaker	Sphinx's Riddle (IOI24_sphinx)	C++20	1.50 / 100	2 ms	412 KiB

sphinx

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

vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
	int n = N, m = (int)X.size();
	vector<int> x = X, y = Y;
	vector<int> par(n), sz(n, 1);
	iota(par.begin(), par.end(), 0);
	auto findd = [&](auto self, int u) -> int
	{
		return par[u] = (par[u] == u ? u : self(self, par[u]));
	};
	auto unite = [&](int u, int v) -> bool
	{
		u = findd(findd, u);
		v = findd(findd, v);
		if (u == v)
			return false;
		if (sz[u] > sz[v])
			swap(u, v);
		sz[v] += sz[u];
		par[u] = v;
		return true;
	};
	vector adj(n, vector<int>());
	for (int i = 0; i < m; i++)
	{
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	for (int i = 0; i < n; i++)
	{
		int l = 0, r = adj[i].size() - 1, ans = -1;
		while (l <= r)
		{
			int md = (l + r) / 2;
			vector<int> e(n, N);
			for (int j = l; j <= md; j++)
				e[adj[i][j]] = -1;
			int cnt = perform_experiment(e);
			e[i] = -1;
			int cnt2 = perform_experiment(e);
			if (n > 2)
			{
				if (cnt == cnt2 and l == md)
				{
					unite(i, adj[i][md]);
				}
			}
			else
			{
				if (cnt2 == 1)
					unite(i, adj[i][md]);
			}
			if (cnt2 == cnt)
			{
				r = md - 1;
			}
			else
			{
				l = md + 1;
			}
		}
		for (int j : adj[i])
			adj[j].erase(find(adj[j].begin(), adj[j].end(), i));
	}
	set<int> st;
	for (int i = 0; i < n; i++)
		st.insert(findd(findd, i));
	int j = 0;
	map<int, int> mp;
	for (auto i : st)
	{
		mp[i] = j++;
	}
	vector<int> res(n);
	for (int i = 0; i < n; i++)
		res[i] = mp[findd(findd, i)];
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36