Submission #829591

#	Time	Username	Problem	Language	Result	Execution time	Memory
829591		Abrar_Al_Samit	Keys (IOI21_keys)	C++17	20 / 100	73 ms	20716 KiB

keys

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

using namespace std;

const int nax = 200;

vector<pair<int,int>>g[nax];
vector<int> find_reachable(vector<int> r, vector<int> u, 
	vector<int> v, vector<int> c) {

	int n = r.size(), m = u.size();
	for(int i=0; i<m; ++i) {
		g[u[i]].emplace_back(v[i], c[i]);
		g[v[i]].emplace_back(u[i], c[i]);
	}

	int cnt[n] = {0};
	for(int sc=0; sc<n; ++sc) {
		bool rc[n] = {0};
		rc[sc] = 1;

		bool key[n] = {0};
		key[r[sc]] = 1;

		while(1) {
			bool none = true;
			for(int i=0; i<n; ++i) if(rc[i]) {
				for(auto [to ,type] : g[i]) {
					if(key[type] && !rc[to]) {
						rc[to] = 1;
						key[r[to]] = 1;
						none = false;
					}
				}
			}
			if(none) break;
		}
		for(int i=0; i<n; ++i) {
			cnt[sc] += rc[i];
		}
	}

	int mn = 1e9;
	for(int i=0; i<n; ++i) {
		mn = min(mn, cnt[i]);
	}

	vector<int>ret(n);
	for(int i=0; i<n; ++i) if(cnt[i]==mn) {
		ret[i] = 1;
	}
	return ret;
}

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