Submission #773411

#	Time	Username	Problem	Language	Result	Execution time	Memory
773411		SanguineChameleon	Keys (IOI21_keys)	C++17	37 / 100	3071 ms	38552 KiB

keys

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

const int maxn = 3e5 + 20;
vector<pair<int, int>> adj[maxn];
vector<pair<int, int>> edges[maxn];
bool flag[maxn];
bool found[maxn];
int cnt[maxn];

vector<int> find_reachable(vector<int> type, vector<int> u, vector<int> v, vector<int> c) {
	int n = type.size();
	int m = u.size();
	for (int i = 0; i < m; i++) {
		adj[u[i]].emplace_back(v[i], c[i]);
		adj[v[i]].emplace_back(u[i], c[i]);
		edges[c[i]].emplace_back(u[i], v[i]);
	}
	int mi = n + 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			flag[j] = false;
			found[j] = false;
		}
		flag[i] = true;
		deque<int> q = {i};
		while (!q.empty()) {
			int u = q.front();
			cnt[i]++;
			q.pop_front();
			found[type[u]] = true;
			for (auto e: edges[type[u]]) {
				if (flag[e.first] && !flag[e.second]) {
					flag[e.second] = true;
					q.push_back(e.second);
				}
				if (flag[e.second] && !flag[e.first]) {
					flag[e.first] = true;
					q.push_back(e.first);
				}
			}
			for (auto e: adj[u]) {
				if (found[e.second] && !flag[e.first]) {
					flag[e.first] = true;
					q.push_back(e.first);
				}
			}
		}
		mi = min(mi, cnt[i]);
	}
	vector<int> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = (cnt[i] == mi);
	}
	return res;
}

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