Submission #1062779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062779		fv3	Keys (IOI21_keys)	C++17	9 / 100	94 ms	20848 KiB

keys

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

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

vector<int> visited;
int DFS(int index)
{
	visited[index] = 1;
	int sz = 0;
	for (auto node : adj[index])
	{
		if (visited[node]) continue;
		sz += DFS(node);
	}
	return sz + 1;
}

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

	vector<int> ans(N);
	int ok = false;
	for (int i = 0; i < N; i++)
	{
		if (r[i] || adj[i].size() == 0)
		{
			ans[i] = 1;
			ok = true;
		}
	}

	if (ok)
		return ans;

	visited = vector<int>(N);
	int mn_size = 1 << 30;
	vector<int> min_components;
	for (int i = 0; i < N; i++)
	{
		if (visited[i]) continue;
		int sz = DFS(i);
		if (sz < mn_size)
		{
			min_components = {};
			mn_size = sz;
		}

		if (sz == mn_size)
			min_components.push_back(i);
	}

	visited = vector<int>(N);
	for (auto node : min_components)
	{
		DFS(node);
	}

	return visited;
}

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