Submission #1124788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124788		Mousa_Aboubaker	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 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 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});
	while(not q.empty())
	{
		auto [u, p, m, c] = q.front();
		q.pop();

		if(vis[u])
			continue;
		vis[u] = true;
		e[u] = -1;
		int x = perform_experiment(e);
		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;
	/*auto dfs = [&](auto self, int u, int m, int c) -> void
	{
		vis[u] = true;
		e[u] = -1;
		int x = perform_experiment(e);
		if(x == c)
		{
			res[u] = m;
			unite(lst, u);
		}
		else
		{
			res[u] = ++m;
			c++;
		}
		for(auto i: adj[u])
		{
			if(vis[i])
				continue;
			lst = u;
			self(self, i, m, c);
		}
	};
	dfs(dfs, 0, -1, 1);
	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: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36