Submission #1246429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246429		RecursiveCo	Keys (IOI21_keys)	C++20	37 / 100	3093 ms	32180 KiB

keys

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

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int N = r.size();
	int M = u.size();
	vector<int> ans(N, 0);
	vector<int> sz(N, 0);
	vector<vector<pair<int, int>>> adjList(N);
	for (int i = 0; i < M; ++i) {
		adjList[u[i]].push_back({v[i], c[i]});
		adjList[v[i]].push_back({u[i], c[i]});
	}
	for (int i = 0; i < N; ++i) {
		vector<bool> key(N, false);
		vector<bool> visited(N, false);
		vector<set<int>> potential(N);
		queue<int> q;
		q.push(i);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			if (visited[v]) continue;
			visited[v] = true;
			++sz[i];
			for (auto con: adjList[v]) {
				if (key[con.second]) {
					q.push(con.first);
				} else {
					potential[con.second].insert(con.first);
				}
			}
			if (!key[r[v]]) {
				key[r[v]] = true;
				while (!potential[r[v]].empty()) {
					q.push(*potential[r[v]].begin());
					potential[r[v]].erase(*potential[r[v]].begin());
				}
			}
		}
	}
	int m = *min_element(sz.begin(), sz.end());
	for (int i = 0; i < N; ++i) if (sz[i] == m) ans[i] = 1;
	//for (int i = 0; i < N; ++i) cout << sz[i];
	return ans;
}

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