Submission #1068910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068910		Boas	Keys (IOI21_keys)	C++17	0 / 100	0 ms	348 KiB

keys

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef set<int> si;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define ALL(x) begin(x), end(x)
#define sz(x) (int)x.size()

vi find_reachable(vi r, vi u, vi v, vi c)
{
	int n = sz(r);
	int m = sz(c);
	vvii adj(n);
	loop(m, i)
	{
		adj[u[i]].pb({v[i], c[i]});
		adj[v[i]].pb({u[i], c[i]});
	}
	int min = n;
	auto firstReachable = [&](int i) -> int
	{
		int key = r[i];
		for (auto [j, keyNeeded] : adj[i])
		{
			if (keyNeeded == key)
			{
				return j;
			}
		}
		return -1;
	};
	vi next(n);
	vi ans(n);
	loop(n, i)
	{
		int j = firstReachable(i);
		if (j == -1)
		{
			min = 1;
			ans[i] = 1;
		}
		else
			next[i] = j;
	}
	if (min == 1)
		return ans;
	vi cycles;
	vi vis(n, -1);
	vi le(n);
	auto dfs = [&](auto &&self, int i, int l, int iter) -> void
	{
		le[i] = l;
		vis[i] = iter;
		int j = next[i];
		if (vis[j] == -1)
			self(self, j, l + 1, iter);
		else if (vis[j] == iter)
		{
			int len = l - le[j] + 1;
			if (len < min)
			{
				min = len;
				cycles = {i};
			}
			else if (len == min)
			{
				cycles.pb(i);
			}
		}
	};
	loop(n, i)
	{
		if (vis[i] == -1)
			dfs(dfs, i, 0, i);
	}
	auto dfs2 = [&](auto &&self, int i) -> void
	{
		ans[i] = 1;
		int j = next[i];
		if (!ans[j])
			self(self, j);
	};
	for (int i : cycles)
		dfs2(dfs2, i);
	return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33