Submission #831396

#	Time	Username	Problem	Language	Result	Execution time	Memory
831396		Minindu206	Keys (IOI21_keys)	C++17	37 / 100	3059 ms	24224 KiB

keys

#include "keys.h"
#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(), m = u.size(), ans = INT_MAX;
	vector<pair<int, int>> adj[n];
	vector<int> p(n), nrooms(n, 0);
	for (int i = 0; i < m; i++)
	{
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	for (int i = 0; i < n; i++)
	{
		vector<int> key(n, 0), vis(n, 0);
		vector<int> lst[n];
		queue<int> q;

		q.push(i);
		key[r[i]] = 1;
		vis[i] = 1;
		while (!q.empty())
		{
			int node = q.front();
			q.pop();
			vector<int> nkeys;

			for (auto pi : adj[node])
			{
				if (!vis[pi.first])
				{
					if (key[pi.second])
					{
						vis[pi.first] = 1;
						q.push(pi.first);
						if (key[r[pi.first]] == 0)
						{
							key[r[pi.first]] = 1;
							nkeys.push_back(r[pi.first]);
						}
					}
					else
						lst[pi.second].push_back(pi.first);
				}
			}
			for (auto k : nkeys)
			{
				for (auto nd : lst[k])
				{
					if (!vis[nd])
					{
						q.push(nd);
						key[r[nd]] = 1;
						vis[nd] = 1;
					}
				}
				lst[k].clear();
			}
		}
		for (int j = 0; j < n; j++)
			nrooms[i] += vis[j];
		ans = min(ans, nrooms[i]);
	}
	for (int i = 0; i < n; i++)
		p[i] = (nrooms[i] == ans);
	return p;
}

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