Submission #574449

#	Time	Username	Problem	Language	Result	Execution time	Memory
574449		wjajjsasqq	Keys (IOI21_keys)	C++17	37 / 100	2051 ms	48016 KiB

keys

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

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

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

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

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;
	}
	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] = -1;
		need[i] = 1;
		go[i] = to[i];
	}
	do {
		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;
			while (!vis[cur]) {
				vis[cur] = it;
				if (go[cur] == -1) break;
				cur = go[cur];
			}
			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);
				}
			}
		}
		memset(need, 0, sizeof need);
		for (int i = 0; i < (int)ii.size(); ++i) need[ii[i]] = 1;
		any = 0;
		for (int i = 0; i < (int)ii.size(); ++i) {
			memset(was, 0, sizeof was);
			memset(wascol, 0, sizeof wascol);
			for (int i = 0; i < n; ++i) unlock[i].clear();
			int start = ii[i];
			std::vector<int> vec;
			vec.push_back(start);
			was[start] = 1;
			int res = -1;
			while (!vec.empty()) {
				int v = vec.back();
				vec.pop_back();
				if (need[find(v)] && find(v) != start) {
					res = find(v);
					break;
				} else if (find(v) != start) top[find(v)] = start;
				int c = r[v];
				if (!wascol[c]) {
					wascol[c] = 1;
					for (int i = 0; i < (int)unlock[c].size(); ++i) if (!was[unlock[c][i]]) {
						was[unlock[c][i]] = 1;
						vec.push_back(unlock[c][i]);
					}
				}
				for (int i = 0; i < (int)g[v].size(); ++i) if (!was[g[v][i].first]) {
					if (wascol[g[v][i].second]) {
						was[g[v][i].first] = 1;
						vec.push_back(g[v][i].first);
					} else unlock[g[v][i].second].push_back(g[v][i].first);
				}
			}
			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: 0 / 30
• Subtask 5: 0 / 33