Submission #813967

#	Time	Username	Problem	Language	Result	Execution time	Memory
813967		LittleCube	Keys (IOI21_keys)	C++17	37 / 100	72 ms	17224 KiB

keys

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

vector<pii> E[2000];
vector<int> out[2000];
int n, m, cv[2000], vis[2000], ans[2000];

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size(), m = u.size();
	vector<int> res(n, 0);
	for (int i = 0; i < m; i++)
	{
		E[u[i]].emplace_back(pii(v[i], c[i]));
		E[v[i]].emplace_back(pii(u[i], c[i]));
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			out[j].clear(), cv[j] = vis[j] = 0;

		queue<int> q;
		q.push(i);
		vis[i] = 1;
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			ans[i]++;
			if(!cv[r[u]])
			{
				cv[r[u]] = 1;
				for (auto v : out[r[u]])
					if(!vis[v])
					{
						vis[v] = 1;
						q.push(v);
					}
				out[r[u]].clear();
			}
			for (auto [v, c] : E[u])
				if(!vis[v])
				{
					if(cv[c])
					{
						vis[v] = 1;
						q.push(v);
					}
					else
						out[c].emplace_back(v);
				}
		}
	}
	int mi = *min_element(ans, ans + n);
	for (int i = 0; i < n; i++)
		res[i] = (mi == ans[i] ? 1 : 0);
	return res;
}

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