Submission #1062843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062843		fv3	Keys (IOI21_keys)	C++17	37 / 100	3050 ms	27900 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>

using namespace std;
int N, M;
vector<vector<pair<int, int>>> adj;
vector<int> R, C;

vector<int> visited;

int find_size(int index)
{
	set<int> keys;

	map<int, vector<int>> locked;
	vector<int> visited(N);
	stack<int> stck;
	stck.push(index);

	int cnt = 0;
	while (!stck.empty())
	{
		int s = stck.top();
		stck.pop();

		if (visited[s]) continue;
		visited[s] = 1;

		cnt++;

		if (!keys.count(R[s]))
		{
			keys.insert(R[s]);
			for (auto node : locked[R[s]])
			{
				if (!visited[node])
					stck.push(node);
			}
		}

		for (auto node : adj[s])
		{
			if (visited[node.first]) continue;
			if (keys.count(node.second))
				stck.push(node.first);
			else
				locked[node.second].push_back(node.first);
		}
	}

	return cnt;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) 
{
	R = r; C = c;
	N = r.size(); M = u.size();
	adj = vector<vector<pair<int, int>>>(N);
	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]});
	}

	vector<int> sz(N);
	int mn_sz = 1 << 30;
	for (int i = 0; i < N; i++)
	{
		sz[i] = find_size(i);
		mn_sz = min(mn_sz, sz[i]);
	}

	vector<int> ans(N);
	for (int i = 0; i < N; i++)
		ans[i] = (sz[i] == mn_sz);
	return ans;
}

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