Submission #1229583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229583		boris_mihov	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	130 ms	1452 KiB

sphinx

#include "sphinx.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 250 + 10;
const int INF  = 1e9;

int n, m;
int color[MAXN];
struct DSU
{
	int par[MAXN];
	std::vector <int> inComponent[MAXN];

	void build()
	{
		for (int i = 1 ; i <= n ; ++i)
		{
			par[i] = i;
			inComponent[i].push_back(i);
		}
	}

	int find(int node)
	{
		if (par[node] == node) return node;
		return par[node] = find(par[node]);
	}

	void connect(int u, int v)
	{
		u = find(u);
		v = find(v);
		if (u == v)
		{
			return;
		}

		if (inComponent[u].size() > inComponent[v].size())
		{
			std::swap(u, v);
		}

		par[u] = v;
		for (const int &x : inComponent[u])
		{
			inComponent[v].push_back(x);
		}
	}

	bool areConnected(int u, int v)
	{
		return find(u) == find(v);
	}
};

struct DSU2
{
	int par[MAXN];
	int dep[MAXN];

	void build()
	{
		for (int i = 1 ; i <= n ; ++i)
		{
			par[i] = i;
			dep[i] = 1;
		}
	}

	int find(int node)
	{
		if (par[node] == node) return node;
		return par[node] = find(par[node]);
	}

	void connect(int u, int v)
	{
		u = find(u);
		v = find(v);
		if (u == v)
		{
			return;
		}

		if (dep[u] > dep[v])
		{
			std::swap(u, v);
		}

		if (dep[u] == dep[v])
		{
			dep[v]++;
		}

		par[u] = v;
	}

	bool areConnected(int u, int v)
	{
		return find(u) == find(v);
	}
};

DSU dsu;
DSU2 dsuQuery;
bool isActive[MAXN];
bool inQueue[MAXN];
std::vector <int> g[MAXN];
int edgeFrom[MAXN * MAXN];
int edgeTo[MAXN * MAXN];
bool wasSeen[MAXN];

int getWorstCase()
{
	dsuQuery.build();
	for (int i = 1 ; i <= m ; ++i)
	{
		if (dsu.areConnected(edgeFrom[i], edgeTo[i]) || (color[edgeFrom[i]] != -1 && color[edgeTo[i]] != -1 && color[edgeFrom[i]] == color[edgeTo[i]]))
		{
			dsuQuery.connect(edgeFrom[i], edgeTo[i]);
		}
	}

	int res = 0;
	std::fill(wasSeen, wasSeen + n + 1, 0);
	for (int i = 1 ; i <= n ; ++i)
	{
		res += !wasSeen[dsuQuery.find(i)];
		wasSeen[dsuQuery.find(i)] = true;
	}

	return res;
}

int query()
{
	std::vector <int> exp_col(n);
	for (int i = 1 ; i <= n ; ++i)
	{
		exp_col[i - 1] = color[i];
	}

	return perform_experiment(exp_col);
}

std::vector <int> find_colours(int N, std::vector <int> X, std::vector <int> Y)
{
	n = N;
	m = X.size();
	for (int i = 0 ; i < m ; ++i)
	{
		X[i]++;
		Y[i]++;
		edgeFrom[i + 1] = X[i];
		edgeTo[i + 1] = Y[i];
		
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}

	std::fill(color + 1, color + 1 + n, n);
	dsu.build();
	
	std::queue <int> q;
	inQueue[1] = true;
	q.push(1);
	
	while (q.size())
	{
		int node = q.front();
		q.pop();
		
		// std::cout << "node: " << node << '\n';
		isActive[node] = true;
		std::set <int> set;
		for (const int &u : g[node])
		{
			if (isActive[u])
			{
				set.insert(dsu.find(u));
			}
		}
		
		std::fill(color + 1, color + 1 + n, n);
		for (const int &comp : set)
		{
			for (const int &u : dsu.inComponent[comp])
			{
				color[u] = -1;
			}
		}

		color[node] = -1;
		int cnt = getWorstCase();
		int res = query();

		if (cnt != res)
		{
			assert(set.size());
			std::vector <int> vals;
			for (const int &comp : set)
			{
				vals.push_back(comp);
			}

			int l = -1, r = (int)vals.size() - 1, mid;
			while (l < r - 1)
			{
				mid = l + r >> 1;
				std::fill(color + 1, color + 1 + n, n);
				for (int i = 0 ; i <= mid ; ++i)
				{
					for (const int &u : dsu.inComponent[vals[i]])
					{
						color[u] = -1;
					}
				}

				color[node] = -1;
				cnt = getWorstCase();
				res = query();

				if (res == cnt) l = mid;
				else r = mid;
			}

			// std::cout << "connect: " << node << ' ' << vals[r] << '\n';
			dsu.connect(node, vals[r]);
		}

		for (const int &u : g[node])
		{
			if (!inQueue[u])
			{
				inQueue[u] = true;
				q.push(u);
			}
		}
	}

	std::vector <int> sol;
	for (int i = 1 ; i <= n ; ++i)
	{
		sol.push_back(dsu.find(i) - 1);
	}

	return sol;
}	

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