Submission #1164031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164031		jairRS	Keys (IOI21_keys)	C++20	37 / 100	3084 ms	25556 KiB

keys

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

struct Edge {
	int to; // destino
	int key; // llave del pasillo
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> p(r.size());
	vector<int> ans(r.size(), 0);
	
	const int n = r.size();
	const int m = c.size();

	vector<vector<Edge>> adj(n);
	for(int j = 0; j < m; ++j){
		int key = c[j];
		adj[u[j]].push_back({v[j], key});
		adj[v[j]].push_back({u[j], key});
	}


	for(int i = 0; i < n; i++){

		vvi key_to_rooms(n);
		vector<bool> visited(n, false);
		vector<bool> have_key(n, false);
		queue<int> rooms;

		rooms.push(i);
		visited[i] = true;
		while(!rooms.empty()){
			int cur = rooms.front();
			rooms.pop();

			int room_key = r[cur];

			if (!have_key[room_key]) {
				for(int new_room : key_to_rooms[room_key]) rooms.push(new_room);
				have_key[room_key] = true;
			}

			for(auto [to, required_key] : adj[cur]){
				if(have_key[required_key] && !visited[to]){
					rooms.push(to);
					visited[to] = true;
				} else if (!have_key[required_key]){
					key_to_rooms[required_key].push_back(to);
				}
			}
		}

		int vis_count = 0;

		for(int i = 0; i < n; i++) 
			vis_count += (visited[i] == true);

		p[i] = vis_count;
	}

	int smallest_p = *min_element(p.begin(), p.end());
	for(int i = 0; i < n; i++) 
		ans[i] = (p[i] == smallest_p);

	return ans;
}

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