Submission #997073

#	Time	Username	Problem	Language	Result	Execution time	Memory
997073		0npata	Keys (IOI21_keys)	C++17	37 / 100	3084 ms	29988 KiB

keys

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

#define vec vector

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();
	int m = u.size();

	vec<vec<pair<int, int>>> g(n);

	for(int i = 0; i<m; i++) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}

	vec<int> reach(n);
	int mn = n;

	for(int i = 0; i<n; i++) {
		vec<bool> vis(n);
		vec<int> stk{i};

		set<int> keys;
		vec<vec<int>> enc_edg(n);

		while(stk.size() > 0) {
			int j = stk.back();
			stk.pop_back();
			if(vis[j]) continue;
			vis[j] = true;
			keys.insert(r[j]);
			for(int k : enc_edg[r[j]]) {
				stk.push_back(k);
			}
			enc_edg[r[j]] = {};
			for(auto e : g[j]) {
				if(keys.find(e.second) != keys.end()) {
					stk.push_back(e.first);
				}
				else {
					enc_edg[e.second].push_back(e.first);
				}
			}
		}

		int reached = 0;
		for(int i = 0; i<n; i++) {
			if(vis[i]) reached++;
		}
		reach[i] = reached;
		mn = min(mn, reach[i]);
	}

	vec<int> ans(n);
	for(int i = 0; i<n; i++) {
		if(reach[i] == mn) ans[i] = 1;
	}

	return ans;
}

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