제출 #1019902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019902		aufan	열쇠 (IOI21_keys)	C++17	100 / 100	656 ms	52668 KiB

keys

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = (int)r.size(), m = (int)u.size();
	vector<vector<pair<int, int>>> g(n);
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
 
	vector<int> par(n);
	iota(par.begin(), par.end(), 0);
 
	function<int(int)> root = [&](int x) {
		return par[x] == x ? x : par[x] = root(par[x]);
	};
 
	vector<int> vis(n), done(n), q(n), p(n, n + 1);
	vector<vector<int>> pend(n);
 
	auto bfs = [&](int s, int upd) {
		int pl = 0, pr = 0, ret = -1;
		vis[s] = 1;
		q[pr++] = s;
		for (int i = 0; i < pr; i++) {
			int x = q[pl++];
 
			if (!done[r[x]]) {
				done[r[x]] = 1;
				for (auto z : pend[r[x]]) {
					if (root(z) != s) {
						ret = root(z);
					}
 
					if (!vis[z]) {
						vis[z] = 1;
						q[pr++] = z;
					}
				}
 
				pend[r[x]].clear();
			}
 
			for (auto [z, y] : g[x]) {
				if (!done[y]) {
					pend[y].push_back(z);
				} else {
					if (root(z) != s) {
						ret = root(z);
					}
 
					if (!vis[z]) {
						vis[z] = 1;
						q[pr++] = z;
					}
				}
			}
 
			if (ret != -1) break;
		}
 
		for (int i = 0; i < pr; i++) {
			int x = q[i];
 
			vis[x] = 0;
		}
 
		for (int i = 0; i < pl; i++) {
			int x = q[i];
 
			done[r[x]] = 0;
			for (auto [z, y] : g[x]) {
				pend[y].clear();
			}
		}
 
		if (upd) {
			for (int i = 0; i < pr; i++) {
				int x = q[i];
 
				p[x] = pr;
			}
		}
 
		return ret;
	};
 
	for (int _ = 0; _ < 20; _++) {
		vector<int> ok(n, 0);
		for (int i = 0; i < n; i++) {
			if (root(i) == i && !ok[i]) {
				int j = bfs(i, 0);
				if (j != -1) {
					par[i] = j;
					ok[j] = 1;
				}
			}
		}
	}	
 
	for (int i = 0; i < n; i++) {
		if (root(i) == i) {
			bfs(i, 1);
		}
	}
 
	int mn = *min_element(p.begin(), p.end());
	vector<int> ans(n);
	for (int i = 0; i < n; i++) ans[i] = (p[i] == mn);
 
	return ans;
}

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