Submission #574289

#	Time	Username	Problem	Language	Result	Execution time	Memory
574289		wjajjsasqq	Keys (IOI21_keys)	C++17	9 / 100	3066 ms	19276 KiB

keys

#include "keys.h"
#include <cassert>
#include <algorithm>

const int N = 2000;
int n, res[N];
bool u[N], vis[N];
int unlock[N][N], sz[N];
std::vector<std::pair<int, int> > g[N];

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = r.size();
	for (int i = 0; i < (int)u.size(); ++i) {
		g[u[i]].push_back(std::make_pair(v[i], c[i]));
		g[v[i]].push_back(std::make_pair(u[i], c[i]));
	}
	std::vector<int> vec;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			u[j] = 0;
			vis[j] = 0;
			sz[j] = 0;
		}
		vec.push_back(i);
		vis[i] = 1;
		while (!vec.empty()) {
			int v = vec.back();
			vec.pop_back();
			++res[i];
			if (v < 0 || v >= n) while (true);
			int c = r[v];
			if (!u[c]) {
				u[c] = 1;
				for (int i = 0; i < sz[c]; ++i) if (!vis[unlock[c][i]]) {
					vis[unlock[c][i]] = 1;
					vec.push_back(unlock[c][i]);
				}
			}
			for (int i = 0; i < (int)g[v].size(); ++i) if (!vis[g[v][i].first]) {
				if (u[g[v][i].second]) {
					vis[g[v][i].first] = 1;
					vec.push_back(g[v][i].first);
				} else unlock[g[v][i].second][sz[g[v][i].second++]] = g[v][i].first;
			}
		}
	}
	int mn = *std::min_element(res, res + n);
	std::vector<int> ans(n);
	for (int i = 0; i < n; ++i) ans[i] = mn == res[i];
	return ans;
}

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