제출 #1053060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053060		MercubytheFirst	열쇠 (IOI21_keys)	C++17	37 / 100	3053 ms	31856 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(n, false);
		waiting.assign(n, 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: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33