Submission #436699

#	Time	Username	Problem	Language	Result	Execution time	Memory
436699		shrimb	Keys (IOI21_keys)	C++17	37 / 100	226 ms	16996 KiB

keys

#include"bits/stdc++.h"
// #define int long long
#define endl '\n'
using namespace std;

vector<pair<int,int>> adj[5001];
unordered_set<int> keys[5001];

vector<int> find_reachable (vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size(), 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]);
	}
	int p[n];
	for (int i = 0 ; i < n ; i++) {
		for (auto& j : keys) j.clear();
		bitset<5001> vis(0);
		bitset<5001> got(0);

		queue<int> process;
		process.push(i);
		vis[i] = 1;
		int cnt = 0;
		while (process.size()) {
			auto cur = process.front();
			cnt++;
			// cerr << cur << endl;
			process.pop();
			got[r[cur]] = 1;
			while (keys[r[cur]].size()) {
				if (!vis[*keys[r[cur]].begin()]) {
					process.push(*keys[r[cur]].begin());
					vis[*keys[r[cur]].begin()] = 1;
				}
				keys[r[cur]].erase(keys[r[cur]].begin());
			}
			for (auto i : adj[cur]) {
				if (got[i.second]) {
					if (!vis[i.first]) {
						process.push(i.first);
						vis[i.first] = 1;
					}
				}
				else if (!vis[i.first]){
					keys[i.second].insert(i.first);
				}
			}
		}
		p[i] = cnt;
		// cerr << p[i] << " ";
	}
	// cerr << endl;
	int x = *min_element(p, p + n);
	vector<int> ret(n);
	for (int i = 0 ; i < n ; i++) if (p[i] == x) ret[i] = 1;
	return ret;

}

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