Submission #1233518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233518		Timosh	Keys (IOI21_keys)	C++20	9 / 100	3089 ms	26832 KiB

keys

#include <bits/stdc++.h>

using namespace std;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
	int n = r.size();
	int m = c.size();
	int mn = n + 1;
	vector<int> ans(n);
	vector<vector<pair<int, int>>> g(n);
	for (int i = 0; i < m; i++)
		g[u[i]].push_back({v[i], c[i]}), g[v[i]].push_back({u[i], c[i]});
	for (int i = 0; i < n; i++)
	{
		vector<int> vis(n), colvis(n);
		vector<vector<int>> col(n);
		queue<int> q;
		q.push(i);
		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			if (vis[x])
				continue;
			vis[x] = 1;
			for (auto &y : g[x])
				col[y.second].push_back(y.first);
			for (auto &y : g[x])
				if (!vis[y.first] && (colvis[c[y.second]] || c[y.second] == r[x]))
					q.push(y.first);
			if (colvis[r[x]])
				continue;
			colvis[r[x]] = 1;
			for (auto &y : col[r[x]])
				if (!vis[y])
					q.push(y);
		}
		for (auto &j : vis)
			ans[i] += j;
	}
	mn = *min_element(ans.begin(), ans.end());
	for (int i = 0; i < n; i++)
		ans[i] = mn == ans[i];
	return ans;
}

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