Submission #1229626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229626		boris_mihov	Sphinx's Riddle (IOI24_sphinx)	C++20	64 / 100	410 ms	4532 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];
std::vector <int> diffGraph[MAXN];
std::vector <int> t[MAXN];
int edgeFrom[MAXN * MAXN];
std::vector <int> part[2];
int edgeTo[MAXN * MAXN];
bool wasSeen[MAXN];
int bigColor[MAXN];
int depth[MAXN];
int answer[MAXN];

bool doneMerging = false;
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);
}

int bigWorstCase()
{
	dsuQuery.build();
	for (int i = 1 ; i <= m ; ++i)
	{
		if (dsu.areConnected(edgeFrom[i], edgeTo[i]) || (bigColor[dsu.find(edgeFrom[i])] != -1 && bigColor[dsu.find(edgeTo[i])] != -1 && bigColor[dsu.find(edgeFrom[i])] == bigColor[dsu.find(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 getWorst2()
{
	dsuQuery.build();
	for (int i = 1 ; i <= m ; ++i)
	{
		if (edgeFrom[i] != 1)
		{
			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 bigQuery()
{
	std::vector <int> exp_col(n);
	for (int i = 1 ; i <= n ; ++i)
	{
		exp_col[i - 1] = bigColor[dsu.find(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();
		
		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();
		int diff = cnt - res;
		int oldR = -1;

		while (diff--)
		{
			assert(set.size());
			std::vector <int> vals;
			for (const int &comp : set)
			{
				vals.push_back(comp);
			}

			int l = oldR, 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;
			}
			
			dsu.connect(node, vals[r]);
			oldR = r;
		}
		
		for (const int &u : g[node])
		{
			if (!inQueue[u])
			{
				inQueue[u] = true;
				q.push(u);
			}
		}
	}
	
	std::set <std::pair <int,int>> added_edges;
	for (int i = 0 ; i < m ; ++i)
	{
		if (dsu.find(X[i]) != dsu.find(Y[i]) && !added_edges.count({dsu.find(X[i]), dsu.find(Y[i])}))
		{
			added_edges.insert({dsu.find(X[i]), dsu.find(Y[i])});
			added_edges.insert({dsu.find(Y[i]), dsu.find(X[i])});
			diffGraph[dsu.find(X[i])].push_back(dsu.find(Y[i]));
			diffGraph[dsu.find(Y[i])].push_back(dsu.find(X[i]));
		}
	}
	
	bool allEqual = true;
	for (int i = 2 ; i <= n ; ++i)
	{
		if (!dsu.areConnected(1, i))
		{
			allEqual = false;
			break;
		}
	}
	
	if (allEqual)
	{
		for (int c = 0 ; c < N ; ++c)
		{
			std::vector <int> toQuery(n, -1);
			for (int j = 0 ; j < n ; ++j)
			{
				color[j + 1] = toQuery[j];
			}
			toQuery[0] = c;
			if (perform_experiment(toQuery) != getWorst2())
			{
				return std::vector <int> (n, c);
			}
		}
		
		assert(false);
	}
	
	std::fill(inQueue, inQueue + 1 + n, 0);
	inQueue[dsu.find(1)] = true;
	q.push(dsu.find(1));
	part[0].push_back(dsu.find(1));
	
	while (q.size())
	{
		int node = q.front();
		q.pop();
		
		for (const int &v : dsu.inComponent[node])
		{
			for (const int &u : g[v])
			{
				if (!inQueue[dsu.find(u)])
				{
					depth[dsu.find(u)] = depth[node] + 1;
					part[depth[dsu.find(u)] & 1].push_back(dsu.find(u));
					t[node].push_back(dsu.find(u));
					inQueue[u] = true;
					q.push(dsu.find(u));
				}
			}
		}
	}

	for (int times = 0 ; times < 2 ; ++times) // curr -> 0; other -> 1
	{
		std::vector <int> found;
		for (int c = 0 ; c < N ; ++c)
		{
			for (const int &u : part[0])
			{
				for (const int &v : dsu.inComponent[u])
				{
					bigColor[v] = -1;
				}
			}
			
			for (const int &u : part[1])
			{
				for (const int &v : dsu.inComponent[u])
				{
					bigColor[v] = c;
				}
			}
			
			for (const int &u : found)
			{
				for (const int &v : dsu.inComponent[u])
				{
					bigColor[v] = answer[v];
				}
			}
			
			int cnt = bigWorstCase();
			int res = bigQuery();
			bool shouldEnd = (cnt == res);
			int lastR = -1;
			int resultR = res;
			while (!shouldEnd)
			{
				int l = lastR, r = part[0].size(), mid;
				while (l < r - 1)
				{
					mid = l + r >> 1;
					std::fill(bigColor + 1, bigColor + 1 + n, n);
					for (const int &u : part[1])
					{
						for (const int &v : dsu.inComponent[u])
						{
							bigColor[v] = c;
						}
					}

					for (int i = 0 ; i <= mid ; ++i)
					{
						for (const int &v : dsu.inComponent[part[0][i]])
						{
							bigColor[v] = -1;
						}
					}

					for (const int &u : found)
					{
						for (const int &v : dsu.inComponent[u])
						{
							bigColor[v] = answer[v];
						}
					}

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

				found.push_back(part[0][r]);
				answer[part[0][r]] = c;
				lastR = r;
				
				for (const int &u : part[0])
				{
					for (const int &v : dsu.inComponent[u])
					{
						bigColor[v] = -1;
					}
				}
				
				for (const int &u : part[1])
				{
					for (const int &v : dsu.inComponent[u])
					{
						bigColor[v] = c;
					}
				}

				for (const int &u : found)
				{
					for (const int &v : dsu.inComponent[u])
					{
						bigColor[v] = answer[v];
					}
				}

				cnt = bigWorstCase();
				shouldEnd = (cnt == resultR);
			}
		}

		std::swap(part[0], part[1]);
	}

	std::vector <int> sol(n);
	for (int i = 0 ; i < n ; ++i)
	{
		sol[i] = answer[dsu.find(i + 1)];
	}

	return sol;
}	

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