제출 #1233411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233411		rythm_of_knight	열쇠 (IOI21_keys)	C++17	37 / 100	3101 ms	248076 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;
int f[N], sz[N];

int father(int x) {
	if (f[x] != f[f[x]])
		return f[x] = father(f[x]);
	return f[x];
}

int target;
queue <int> q;
vector <int> com[N];
int vis[N], r[N];

void dsu(int a, int b) {
	a = father(a), b = father(b);
	if (a == b)
		return;
	if (a == father(target)) {
		for (int i : com[b]) {
			if (!vis[r[i]]) {
				vis[r[i]] = 1;
				q.push(r[i]);
			}
		}
	} else if (b == father(target)) {
		for (int i : com[a]) {
			if (!vis[r[i]]) {
				vis[r[i]] = 1;
				q.push(r[i]);
			}
		}
	}
	if (sz[a] < sz[b])
		swap(a, b);
	for (int i : com[b])
		com[a].push_back(i);
	f[b] = a;
	sz[a] += sz[b];
}

vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
	int n = R.size(), m = u.size();
	for (int i = 0; i < n; i++)
		r[i] = R[i];
	vector<int> ans(n, 1), p(n);
	vector <int> g[n];
	for (int i = 0; i < m; i++)
		g[c[i]].push_back(i);
	int mn = n + 1;
	for (int cur = 0; cur < n; cur++) {
		for (int i = 0; i < n; i++)
			f[i] = i, sz[i] = 1, com[i] = {i};
		target = cur;
		for (int i = 0; i < n; i++)
			vis[i] = 0;
		q.push(r[cur]);
		vis[r[cur]] = 1;
		while (!q.empty()) {
			int x = q.front(); q.pop();
			for (int j : g[x])
				dsu(u[j], v[j]);
		}
		p[cur] = sz[father(cur)];
		mn = min(mn, p[cur]);
	}
	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: 0 / 30
• Subtask 5: 0 / 33