Submission #443463

#	Time	Username	Problem	Language	Result	Execution time	Memory
443463		mjhmjh1104	Keys (IOI21_keys)	C++17	37 / 100	3064 ms	37104 KiB

keys

#include "keys.h"
#include <queue>
#include <tuple>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;

bool found[300006], visited[300006], visited_edge[300006];
vector<tuple<int, int, int>> adj[300006];
vector<pair<int, int>> lt[300006];

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	queue<int> q;
	function<void (int)> dfs = [&](int v) {
		for (auto &i: lt[r[v]]) if (!visited[i.second]) {
			visited[i.second] = true;
			q.push(i.second);
			if (!found[r[i.second]]) {
				found[r[i.second]] = true;
				dfs(i.second);
			}
		}
	};
	int n = (int)r.size(), m = (int)c.size();
	for (int i = 0; i < m; i++) {
		adj[u[i]].push_back({ v[i], c[i], i });
		adj[v[i]].push_back({ u[i], c[i], i });
	}
	vector<int> ans(n), p;
	for (int i = 0; i < n; i++) {
		fill(found, found + n, false);
		fill(visited, visited + n, false);
		fill(visited_edge, visited_edge + m, false);
		for (int i = 0; i < n; i++) lt[i].clear();
		visited[i] = true;
		found[r[i]] = true;
		while (!q.empty()) q.pop();
		q.push(i);
		while (!q.empty()) {
			int t = q.front(); q.pop();
			for (auto &i: adj[t]) if (!visited_edge[get<2>(i)]) {
				auto [ v, c, j ] = i;
				visited_edge[j] = true;
				if (found[c]) {
					if (!visited[v]) {
						visited[v] = true;
						q.push(v);
						if (!found[r[v]]) {
							found[r[v]] = true;
							dfs(v);
						}
					}
				} else lt[c].push_back({ j, v });
			}
		}
		int cnt = 0;
		for (int i = 0; i < n; i++) if (visited[i]) cnt++;
		p.push_back(cnt);
	}
	int globalMin = *min_element(p.begin(), p.end());
	for (int i = 0; i < n; i++) ans[i] = (globalMin == p[i]);
	return ans;
}

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