Submission #436099

#	Time	Username	Problem	Language	Result	Execution time	Memory
436099		Mohammed_Atalah	Keys (IOI21_keys)	C++17	20 / 100	2536 ms	1048580 KiB

keys

#include <vector>
#include <bits/stdc++.h>

using namespace std;

vector<int> vis;
vector<vector<vector<int>>> edg;
vector<int> reach;
set<int> keys;
int curr;
vector<int> k;


void dfs(int num) {
	for (auto e : keys) {
		vector<int> con;
		con = edg[e][num];
		for (auto v : con) {
			if (vis[v] != 1) {
				vis[v] = 1;
				keys.insert(k[v]);
				curr++;
				dfs(v);
			}
		}
	}
}


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	k = r;
	int rooms = r.size();
	vis.resize(rooms);
	edg.resize(rooms);
	reach.resize(rooms);
	for (int i = 0; i < rooms; i++) {
		edg[i].resize(rooms);
	}

	int e = u.size();

	for (int i = 0; i < e; i++) {
		edg[c[i]][u[i]].push_back(v[i]);
		edg[c[i]][v[i]].push_back(u[i]);
	}

	for (int i = 0; i < rooms; i++) {
		keys.insert(r[i]);
		curr = 1;
		vis[i] = 1;
		dfs(i);
		// cout << "hello" << endl;
		reach[i] = curr;
		vis.clear();
		vis.resize(rooms);
		keys.clear();
	}

	int mn = reach[0];
	for (int i = 1; i < rooms; i ++) {
		if (reach[i] < mn) {
			mn = reach[i];
		}
	}

	vector<int> res;
	res.resize(rooms);
	for (int i = 0; i < rooms; i++) {
		if (reach[i] != mn) {
			res[i]  = 0;
		} else {
			res[i] = 1;
		}
	}




	return res;
}

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