Submission #1022171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022171		HappyCapybara	Keys (IOI21_keys)	C++17	37 / 100	3018 ms	23212 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(), m = u.size();
	vector<vector<int>> g(n);
	unordered_map<int,vector<int>> k;
	for (int i=0; i<m; i++){
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
		k[c[i]].push_back(i);
	}
	vector<int> res(n, 0);
	for (int i=0; i<n; i++){
		vector<bool> reach(m), seen(n), kf(n);
		queue<int> q;
		q.push(i);
		while (!q.empty()){
			int cur = q.front();
			q.pop();
			if (seen[cur]) continue;
			seen[cur] = true;
			res[i]++;
			for (int next : g[cur]){
				if (!reach[next] && kf[c[next]]){
					if (u[next] != cur) q.push(u[next]);
					else q.push(v[next]);
				}
				reach[next] = true;
			}
			if (!kf[r[cur]]){
				for (int next : k[r[cur]]){
					if (reach[next]){
						q.push(u[next]);
						q.push(v[next]);
					}
				}
			}
			kf[r[cur]] = true;
		}
	}
	int mnm = n;
	for (int x : res) mnm = min(mnm, x);
	vector<int> ans(n, 0);
	for (int i=0; i<n; i++){
		if (res[i] == mnm) 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