Submission #809085

#	Time	Username	Problem	Language	Result	Execution time	Memory
809085		puppy	Keys (IOI21_keys)	C++17	37 / 100	301 ms	18180 KiB

keys

#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
vector<pair<int, int>> adj[2005];
int p[2005];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int N = r.size(), M = u.size();
	for (int i = 0; i < M; i++) {
		adj[u[i]].push_back(make_pair(c[i], v[i]));
		adj[v[i]].push_back(make_pair(c[i], u[i]));
	}
	for (int i = 0; i < N; i++) {
		bool visited[2005] = {};
		bool found[2005] = {};
		queue<int> reach, q[2005];
		reach.push(i);
		visited[i] = true;
		while (!reach.empty()) {
			int cur = reach.front(); reach.pop();
			if (!found[r[cur]]) {
				found[r[cur]] = true;
				while (!q[r[cur]].empty()) {
					int nxt = q[r[cur]].front(); q[r[cur]].pop();
					if (!visited[nxt]) {
						visited[nxt] = true;
						reach.push(nxt);
					}
				}
			}
			for (pair<int, int> p:adj[cur]) {
				if (!found[p.first]) {
					q[p.first].push(p.second);
				}
				else {
					if (!visited[p.second]) {
						visited[p.second] = true;
						reach.push(p.second);
					}
				}
			}
		}
		for (int j = 0; j < N; j++) p[i] += visited[j];
	}
	int mn = *min_element(p, p + N);
	vector<int> ans(N);
	for (int i = 0; i < N; i++) ans[i] = mn == p[i];
	return ans;
}

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