Submission #1043286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043286		parsadox2	Keys (IOI21_keys)	C++17	37 / 100	66 ms	21076 KiB

keys

#include <vector>
#include "keys.h"
#define F first
#define S second
using namespace std;

const int N = 2e3 + 10;
int n , m , col[N] , p[N];
vector <pair<int , int>> adj[N];
bool marked[N] , key[N];
vector <int> to[N] , can;

void Add_vert(int v)
{
	for(auto u : adj[v])
	{
		if(key[u.F])
			can.push_back(u.S);
		else
			to[u.F].push_back(u.S);
	}
}

void Add_col(int v)
{
	for(auto u : to[v])
		can.push_back(u);
	to[v].clear();
}

void Solve(int star)
{
	vector <int> all;
	all.push_back(star);
	marked[star] = true;
	while(!all.empty())
	{
		int v = all.back();  all.pop_back();
		key[col[v]] = true;
		Add_vert(v);
		Add_col(col[v]);
		while(!can.empty())
		{
			int u = can.back();  can.pop_back();
			if(!marked[u])
			{
				marked[u] = true;
				all.push_back(u);
			}
		}
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size();
	m = u.size();
	for(int i = 0 ; i < n ; i++)
		col[i] = r[i];
	for(int i = 0 ; i < m ; i++)
	{
		adj[u[i]].push_back(make_pair(c[i] , v[i]));
		adj[v[i]].push_back(make_pair(c[i] , u[i]));
	}
	int mn = N;
	for(int i = 0 ; i < n ; i++)
	{
		Solve(i);
		p[i] = 0;
		for(int j = 0 ; j < n ; j++)
		{
			p[i] += marked[j];
			marked[j] = false;
			key[j] = false;
			to[j].clear();
		}
		mn = min(mn , p[i]);
	}
	vector <int> ans(n);
	for(int i = 0 ; i < n ; i++)
	{
		if(p[i] == mn)
			ans[i] = 1;
		else
			ans[i] = 0;
	}
	return ans;
}

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