Submission #1267717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267717		LucaLucaM	Keys (IOI21_keys)	C++20	100 / 100	2772 ms	104656 KiB

keys

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>

// https://mzhang2021.github.io/cp-blog/library/
struct SCC {
	int n;
	std::vector<std::vector<int>> g, gg;
	std::vector<int> order, cur;
	std::vector<bool> vis;
	std::vector<int> root;

	void init(int _n)  {
		n = _n;
		g.resize(n);
		gg.resize(n);
		vis.assign(n, false);
		root.resize(n);
		order.clear();
		cur.clear();
		for (int i = 0; i < n; i++) {
			g[i].clear();
			gg[i].clear();
		}
	}

	void addEdge(int u, int v) {
		g[u].push_back(v);
		gg[v].push_back(u);
	}

	void dfs0(int u) {
		vis[u] = true;
		for (int v : g[u]) {
			if (!vis[v]) {
				dfs0(v);
			}
		}
		order.push_back(u);
	}

	void dfs(int u) {
		vis[u] = true;
		cur.push_back(u);
		for (int v : gg[u]) {
			if (!vis[v]) {
				dfs(v);
			}
		}
	}

	void build() {
		vis.assign(n, false);
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.assign(n, false);
		std::reverse(order.begin(), order.end());
		for (int u : order) { 
			if (!vis[u]) {
				cur.clear();
				dfs(u);
				for (int v : cur) {
					root[v] = cur[0];
				}
			}
		}
	}
};

std::vector<int> find_reachable(std::vector<int> a, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	int n = (int) a.size();
	int m = (int) U.size();
	
	U.resize(2 * m);
	V.resize(2 * m);
	C.resize(2 * m);
	for (int i = m; i < 2 * m; i++) {
		U[i] = V[i - m];
		V[i] = U[i - m];
		C[i] = C[i - m];
	}
	m *= 2;

	std::vector<int> root(n);
	for (int i = 0; i < n; i++) {
		root[i] = i;
	}

	SCC g;

	for (int phase = 0; phase < 20; phase++) {
		std::vector<std::set<int>> keys(n);
		for (int i = 0; i < n; i++) {
			keys[root[i]].insert(a[i]);
		}

		g.init(n);

		for (int i = 0; i < m; i++) {
			int u = U[i], v = V[i];
			int c = C[i];
			if (root[u] == root[v] || keys[root[u]].count(c)) {
				g.addEdge(u, v);
			}
		}


		g.build();

		for (int i = 0; i < n; i++)  {
			root[i] = g.root[i];
		}
	}

	std::vector<int> sz(n, 0);

	for (int i = 0; i < n; i++) {
		sz[root[i]]++;
	}

	std::vector<bool> hasOut(n, false);

	std::vector<std::set<int>> keys(n);
	for (int i = 0; i < n; i++) {
		keys[root[i]].insert(a[i]);
	}
	for (int i = 0; i < m; i++) {
		int u = U[i], v = V[i];
		int c = C[i];
		if (root[u] != root[v] && keys[root[u]].count(c)) {
			hasOut[root[u]] = true;
		}
	}

	int minSize = n;

	for (int i = 0; i < n; i++) {
		if (!hasOut[root[i]]) {
			minSize = std::min(minSize, sz[root[i]]);
		}
	}

	std::vector<int> ret(n, 0);

	for (int i = 0; i < n; i++) {
		if (!hasOut[root[i]]) {
			if (sz[root[i]] == minSize) {
				ret[i] = 1;
			} 
		}
	}

	return ret;
}

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