Submission #693029

#	Time	Username	Problem	Language	Result	Execution time	Memory
693029		zeroesandones	Keys (IOI21_keys)	C++17	20 / 100	3077 ms	13156 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;

using ll = long long;
using vi = vector<ll>;

#define pb emplace_back

const int mxN = 2005;

int get(int x, int n, int m, vector<int>& r, vector<int>& u, vector<int>& v, vector<int>& c) {
	bool vis[n] = {};
	bool key[n] = {};

	vis[x] = true;
	key[r[x]] = true;

	while(true) {
		bool relax = false;
		for(int i = 0; i < m; ++i) {
			if(key[c[i]]) {
				if(vis[u[i]] && !vis[v[i]]) {
					vis[v[i]] = true;
					key[r[v[i]]] = true;
					relax = true;
				} else if(vis[v[i]] && !vis[u[i]]) {
					vis[u[i]] = true;
					key[r[u[i]]] = true;
					relax = true;
				}
			}
		}

		if(!relax) break;
	}

	ll ans = 0;
	for(int i = 0; i < n; ++i) {
		if(vis[i]) ++ans;
	}

	return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();
	int p[n] = {};

	for(int i = 0; i < n; ++i) {
		p[i] = get(i, n, m, r, u, v, c);
	}

	ll mn = *min_element(p, p + n);

	vector<int> ans(n, 1);
	for(int i = 0; i < n; ++i) {
		ans[i] = (p[i] == mn);
	}

	return ans;
}

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