Submission #1201522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201522		HappyCapybara	Keys (IOI21_keys)	C++17	37 / 100	3096 ms	46120 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<int> res(n, 0);
	int smol = n+1;
	map<int,vector<int>> e;
	for (int i=0; i<m; i++) e[c[i]].push_back(i);
	vector<vector<int>> g(n);
	for (int i=0; i<m; i++){
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
	}
	for (int i=0; i<n; i++){
		vector<bool> seen(n, false), done(m, false);
		set<int> rch, unlk;
		queue<int> q;
		q.push(i);
		while (!q.empty()){
			int cur = q.front();
			q.pop();
			if (seen[cur]) continue;
			seen[cur] = true;
			res[i]++;
			if (!done[r[cur]]){
				for (int next : e[r[cur]]){
					if (unlk.find(next) != unlk.end()) continue;
					unlk.insert(next);
					if (rch.find(next) != rch.end()){
						q.push(u[next]);
						q.push(v[next]);
					}
				}
			}
			done[r[cur]] = true;
			for (int next : g[cur]){
				if (rch.find(next) != rch.end()) continue;
				rch.insert(next);
				if (unlk.find(next) != unlk.end()) q.push(u[next]+v[next]-cur);
			}
		}
		smol = min(smol, res[i]);
	}
	vector<int> ans(n);
	for (int i=0; i<n; i++) ans[i] = (res[i] == smol);
	return ans;
}

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