Submission #1124866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124866		Mousa_Aboubaker	Sphinx's Riddle (IOI24_sphinx)	C++20	1.50 / 100	62 ms	1432 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 find = [&](auto self, int u) -> int
	{
		return par[u] = (par[u] == u ? u : self(self, par[u]));
	};
	auto unite = [&](int u, int v) -> bool
	{
		u = find(find, u);
		v = find(find, 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(auto &i: adj)
		sort(i.begin(), i.end());
	vector<bool> vis(n, false);
	vector<int> e(n, n);
	vector<int> res(n, 0);
	int curr = -1;
	int cnt = 1;
	int lst = 0;
	/*queue<tuple<int, int, int, int>> q;
	q.push({0, -1, -1, 1});
	int ss = 0;
	while(not q.empty())
	{
		auto [u, p, m, c] = q.front();
		q.pop();

		if(vis[u])
			continue;
		ss++;
		vis[u] = true;
		e[u] = -1;
		int x = perform_experiment(e);
		if(ss == n)
		{
			if(x == c - 1)
			{
				res[u] = m;
				unite(u, p);
			}
			else
			{
				res[u] = ++m;
				c++;
			}
			break;
		}
		if(x == c)
		{
			res[u] = m;
			unite(u, p);
		}
		else
		{
			res[u] = ++m;
			c++;
		}
		for(auto i: adj[u])
		{
			if(vis[i])
				continue;
			q.push({i, u, m, c});
		}
	}
	return res;*/
	/*int ss = 0;
	auto dfs = [&](auto self, int u, int m, int c) -> void
	{
		vis[u] = true;
		e[u] = -1;
		int x = perform_experiment(e);
		ss++;
		if(ss == n)
		{
			if(x == cnt - 1)
			{
				//res[u] = m;
				unite(lst, u);
			}
			//else
				//res[u] = ++m;
			return;
		}
		if(x == cnt)
		{
			//res[u] = m;
			unite(lst, u);
		}
		else
		{
			//res[u] = ++m;
			cnt++;
		}
		for(auto i: adj[u])
		{
			if(vis[i])
				continue;
			lst = u;
			e[i] = -1;
			self(self, i, m, c);
			e[i] = n;
		}
	};
	dfs(dfs, 0, -1, 1);*/
	/// Todo: finding cycles and connect the vertices using this cycles
	for(int i = 0; i < n; i++)
	{
		e.assign(n, n);
		e[i] = -1;
		vis[i] = true;
		for(auto j: adj[i])
		{
			if(vis[j])
				continue;
			e[j] = -1;
			int x = perform_experiment(e);
			int z = (int)adj[i].size() + (int)adj[j].size() - 2;
			// cout << i << ' ' << j << ' ' << z << '\n';
			if(n == 2)
			{
				if(x == 1)
					unite(i, j);
			}
			else if(x == 2)
				unite(i, j);
			e[j] = n;
		}
	}
	set<int> st;
	map<int, int> mp;
	curr = 0;
	for(int i = 0; i < n; i++)
	{
		if(st.find(find(find, i)) == st.end())
		{
			st.insert(find(find, i));
			mp[find(find, i)] = res[i] = curr++;
		}
		else
		{
			res[i] = mp[find(find, i)];
		}
	}
	return res;
	/*for(int i = 0; i < n; i++)
	{
		e.assign(n, -1);
		for(int j = 0; j < n; j++)
		{
			for(int k = 0; k < n; k++)
			{
				if(k == i)
					continue;
				e[k] = j;
			}
			int m = perform_experiment(e);
			if(m == 1)
			{
				res[i] = j;
				break;
			}
		}
	}
	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