Submission #602160

#	Time	Username	Problem	Language	Result	Execution time	Memory
602160		Drew_	Keys (IOI21_keys)	C++17	37 / 100	109 ms	20936 KiB

keys

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;

const int MAX = 2069;

bitset<MAX> vst, key;
vector<ii> adj[MAX];
vector<int> pend[MAX];

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
	int N = (int)r.size(), M = (int)u.size();
	for (int i = 0; i < M; ++i)
	{
		adj[u[i]].pb({v[i], c[i]});
		adj[v[i]].pb({u[i], c[i]});
	}

	vector<int> ans(r.size(), 1);	
	for (int st = 0; st < N; ++st)
	{
		vst.reset(); key.reset();
		for (int i = 0; i < N; ++i)
			pend[i].clear();

		queue<int> q;

		vst[st] = true;
		q.push(st);

		while (!q.empty())
		{
			int node = q.front();
			q.pop();

			key[r[node]] = true;
			for (int to : pend[r[node]]) if (!vst[to])
			{
				vst[to] = true;
				q.push(to);
			}
			pend[r[node]].clear();

			for (auto [to, id] : adj[node]) if (!vst[to])
			{
				if (key[id])
				{
					vst[to] = true; 
					q.push(to);
				}
				else
				{
					pend[id].pb(to);
				}
			}
		}

		ans[st] = (int)vst.count();
	}

	int mn = *min_element(ans.begin(), ans.end());
	for (int &x : ans)
		x = x == mn;

	return ans;
}

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