Submission #1053057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053057		MercubytheFirst	Keys (IOI21_keys)	C++17	0 / 100	0 ms	348 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
vector<signed> find_reachable(vector<signed> r, vector<signed> u, vector<signed> v, vector<signed> c) {
	int n = r.size();
	int m = u.size();
	vector<vector<pii> > 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]});
	}
	vector<bool> vis, got_key;
	vector<vector<int> > waiting;
	auto reach_dfs = [&](auto&& dfs, int node) -> void
	{
		assert(node < (int)vis.size() and node >= 0);
		if (vis[node]) {
			return;
		}
		vis[node] = true;
		// cout << "hi " << node << ' ' << r[node] << endl;
		// assert(0 <= r[node] and r[node] < (int)got_key.size());
		got_key[r[node]] = true;
		while(!waiting[r[node]].empty()) {
			if(!vis[ waiting[r[node]].back() ]) {
				int to = waiting[r[node]].back();
				assert(0 <= to and to < n);
				waiting[r[node]].pop_back();
				dfs(dfs, to);
			}
			else {
				waiting[r[node]].pop_back();
			}
		}
		for(auto [to, key] : g[node]) {
			if(vis[to]) {
				continue;
			}
			else if(!got_key[key]) {
				assert(to < n);
				waiting[key].push_back(to);
			}
			else {
				dfs(dfs, to);
			}
 
		}
	};
	vector<int> ans(n);
	for(int i = 0; i < n; ++i) {
		vis.assign(n, false);
		got_key.assign(m, false);
		waiting.assign(m, vector<int>());
		reach_dfs(reach_dfs, i);
		ans[i] = count(vis.begin(), vis.end(), true);
		// cout << i << " : ";
		// for(int j = 0; j < n; ++j)
		// 	cout << vis[j] << ' ';
		// cout << " : ";
		// for(int j = 0; j < m; ++j) {
		// 	cout << got_key[j] << ' ';
		// }
		// cout << endl;
	}
	int mn = *min_element(ans.begin(), ans.end());
	for(int& x : ans)
		x = (x == mn);
	return ans;
}
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
 
 
*/

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