Submission #1273156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273156		nicolo_010	Keys (IOI21_keys)	C++20	100 / 100	2506 ms	111612 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int LOG = 20;

struct SCC {

	vector<vector<int>> adj, vadj;
	stack<int> s;
	vector<int> scc;
	vector<bool> vis;
	vector<int> parent;

	SCC(int n) {
		parent.resize(n);
		for (int i=0; i<n; i++) {
			parent[i] = i;
		}
	}

	void init(int n) {
		adj.resize(n);
		vadj.resize(n);
		vis.assign(n, false);
		for (int i=0; i<n; i++) {
			adj[i].clear();
			vadj[i].clear();
		}
	}

	void add(int a, int b) {
		adj[a].push_back(b);
		vadj[b].push_back(a);
	}

	void dfs1(int n) {
		vis[n] = true;
		for (auto x : adj[n]) {
			if (!vis[x]) {
				dfs1(x);
			}
		}
		s.push(n);
	}

	void dfs2(int n) {
		vis[n] = true;
		scc.push_back(n);
		for (auto x : vadj[n]) {
			if (!vis[x]) {
				dfs2(x);
			}
		}
	}

	void process(int n) {
		vis.assign(n, false);
		for (int i=0; i<n; i++) {
			if (!vis[i]) {
				dfs1(i);
			}
		}
		vis.assign(n, false);
		while (!s.empty()) {
			int u = s.top();
			s.pop();
			if (!vis[u]) {
				scc.clear();
				dfs2(u);
				for (auto x : scc) {
					parent[x] = scc[0];
				}
			}
		}
	}

};


vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
	int n = r.size();
	int m = U.size();
	vector<vector<pii>> adj(n);
	vector<int> p(n, 0);
	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;
	SCC kos(n);
	for (int t=0; t<LOG; t++) {
		vector<set<int>> keys(n);
		for (int i=0; i<n; i++) {
			keys[kos.parent[i]].insert(r[i]);
		}
		kos.init(n);
		for (int i=0; i<m; i++) {
			int u = U[i];
			int v = V[i];
			int c = C[i];
			if (kos.parent[u] == kos.parent[v] || keys[kos.parent[u]].count(c)) {
				kos.add(u, v);
			}
		}

		kos.process(n);
	}
	vector<int> sz(n, 0);
	for (int i=0; i<n; i++) {
		sz[kos.parent[i]]++;
	}
	vector<bool> valid(n, true);
	vector<set<int>> keys(n);
	for (int i=0; i<n; i++) {
		keys[kos.parent[i]].insert(r[i]);
	}
	for (int i=0; i<m; i++) {
		int u = U[i];
		int v = V[i];
		int c = C[i];
		if (kos.parent[u] != kos.parent[v] && keys[kos.parent[u]].count(c)) {
			valid[kos.parent[u]] = false;
		}
	}
	int mn = 1e9;
	for (int i=0; i<n; i++) {
		if (valid[kos.parent[i]]) mn = min(mn, sz[kos.parent[i]]);
	}
	vector<int> ans(n, 0);
	for (int i=0; i<n; i++) {
		if (valid[kos.parent[i]] && sz[kos.parent[i]] == mn) {
			ans[i] = 1;
		}
	}
	return ans;
}

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