Submission #574603

#	Time	Username	Problem	Language	Result	Execution time	Memory
574603		wjajjsasqq	Keys (IOI21_keys)	C++17	100 / 100	439 ms	67624 KiB

keys

#include "keys.h"
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 300000;
int n, to[N], top[N], go[N], vis[N], size[N], from[N], wascol[N], was[N], leave[N], top1[N];
std::vector<std::pair<int, int> > g[N];
std::vector<int> unlock[N], t[N];
bool need[N];

int find(int v) {
	if (top[v] == -1) return v;
	return top[v] = find(top[v]);
}

int find1(int v) {
	if (top1[v] == -1) return v;
	return top1[v] = find1(top1[v]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) top[b] = a;
}

void dfs(int v, int x) {
	if (from[v] != -1) return;
	from[v] = x;
	for (int i = 0; i < (int)t[v].size(); ++i) dfs(t[v][i], x);
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = r.size();
	for (int i = 0; i < n; ++i) to[i] = -1;
	for (int i = 0; i < (int)u.size(); ++i) {
		g[u[i]].push_back(std::make_pair(v[i], c[i]));
		g[v[i]].push_back(std::make_pair(u[i], c[i]));
	}
	std::vector<int> ans(n);
	bool any = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < (int)g[i].size(); ++j) if (g[i][j].second == r[i]) to[i] = g[i][j].first;
		if (to[i] == -1) any = 1;
		else t[to[i]].push_back(i);
	}
	if (any) {
		for (int i = 0; i < n; ++i) if (to[i] == -1) ans[i] = 1;
		return ans;
	}
	for (int i = 0; i < n; ++i) {
		top[i] = top1[i] = -1;
		need[i] = 1;
		go[i] = to[i];
	}
	int it = 0;
	do {
		++it;
		assert(it <= 20);
		std::vector<int> ii;
		memset(vis, 0, sizeof vis);
		int it = 0;
		for (int i = 0; i < n; ++i) if (need[i] && !vis[i] && top[i] == -1) {
			++it;
			int cur = i;
			std::vector<int> vv;
			while (!vis[cur]) {
				vis[cur] = it;
				vv.push_back(cur);
				if (go[cur] == -1) break;
				cur = go[cur];
				if (go[cur] == -1) top1[i] = go[i];
			}
			if (vis[cur] == it) {
				if (go[cur] == -1) ii.push_back(cur);
				else {
					int start = cur;
					do {
						merge(cur, go[cur]);
						cur = go[cur];
					} while (cur != start);
					cur = find(cur);
					ii.push_back(cur);
				}
			}
			for (int i = 0; i < (int)vv.size(); ++i) if (vv[i] != cur) top1[vv[i]] = cur;
		}
		memset(need, 0, sizeof need);
		for (int i = 0; i < (int)ii.size(); ++i) need[ii[i]] = 1;
		for (int i = 0; i < n; ++i) from[i] = find1(i);
		any = 0;
		int dit = 0;
		memset(was, 0, sizeof was);
		memset(wascol, 0, sizeof wascol);
		std::vector<int> total(n);
		for (int i = 0; i < (int)ii.size(); ++i) {
			++dit;
			int start = ii[i];
			std::vector<int> vec;
			vec.push_back(start);
			was[start] = dit;
			int res = -1;
			std::vector<int> cc;
			while (!vec.empty() && res == -1) {
				int v = vec.back();
				vec.pop_back();
				if (find(v) != start && need[find(v)]) res = find(v);
				else if (from[v] != start) res = from[v];
				else {
					int c = r[v];
					if (find(v) != start) top[find(v)] = start;
					++total[v];
					assert(total[v] < 2);
					if (wascol[c] != dit) {
						wascol[c] = dit;
						for (int i = 0; i < (int)unlock[c].size(); ++i) if (was[unlock[c][i]] != dit) {
							int next = unlock[c][i];
							was[next] = dit;
							vec.push_back(next);
						}
					}
					if (res == -1) for (int i = 0; i < (int)g[v].size(); ++i) if (was[g[v][i].first] != dit) {
						if (wascol[g[v][i].second] == dit) {
							int next = g[v][i].first;
							was[next] = dit;
							vec.push_back(next);
						} else {
							cc.push_back(g[v][i].second);
							unlock[g[v][i].second].push_back(g[v][i].first);
						}
					}
				}
			}
			for (int i = 0; i < (int)cc.size(); ++i) unlock[cc[i]].clear();
			go[start] = res;
			if (res != -1) any = 1;
		}
	} while (any);
	for (int i = 0; i < n; ++i) if (need[find(i)]) ++size[find(i)];
	int mn = n;
	for (int i = 0; i < n; ++i) if (need[i] && top[i] == -1) mn = std::min(mn, size[i]);
	for (int i = 0; i < n; ++i) if (need[find(i)] && size[find(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