Submission #1242868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242868		AMnu	Keys (IOI21_keys)	C++20	100 / 100	424 ms	55480 KiB

keys

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;

const int MAXN = 3e5+5;

int N, M, P[MAXN];
int vis[MAXN], key[MAXN], emp[MAXN], day;
vector <int> K, ans, now, all, cut[MAXN];
vector <pii> cand, adj[MAXN];

int find(int x) {
	if (P[x] == x) {
		return x;
	}
	return P[x] = find(P[x]);
}

void join(int x,int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		P[x] = y;
	}
}

int bfs(int x,bool t) {
	queue <int> Q;
	Q.push(x);
	vis[x] = day;
	while (!Q.empty()) {
		int y = Q.front();
		Q.pop();
		if (find(x) != find(y)) {
			return y;
		}
		if (t) {
			now.push_back(y);
		}
		if (key[K[y]] != day && emp[K[y]] == day) {
			for (int z : cut[K[y]]) {
				if (vis[z] == day) continue;
				Q.push(z);
				vis[z] = day;
			}
		}
		key[K[y]] = day;
		for (pii z : adj[y]) {
			if (vis[z.fi] == day) continue;
			if (key[z.se] == day) {
				Q.push(z.fi);
				vis[z.fi] = day;
			}
			else {
				if (emp[z.se] != day) {
					emp[z.se] = day;
					cut[z.se].clear();
				}
				cut[z.se].push_back(z.fi);
			}
		}
	}
	return -1;
}

vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c) {
	N = r.size();
	K = r;
	ans = vector<int>(N);
	for (int i=0;i<(int)c.size();i++) {
		adj[u[i]].push_back({v[i],c[i]});
		adj[v[i]].push_back({u[i],c[i]});
	}
	for (int i=0;i<N;i++) {
		P[i] = i;
	}
	do {
		cand.clear();
		for (int i=0;i<N;i++) {
			if (find(i) == i) {
				day++;
				int x = bfs(i,0);
				if (x != -1) {
					cand.push_back({i,x});
				}
			}
		}
		for (pii x : cand) {
			join(x.fi,x.se);
		}
	}
	while (!cand.empty());
	M = N+1;
	for (int i=0;i<N;i++) {
		if (find(i) == i) {
			now.clear();
			day++;
			bfs(i,1);
			if ((int)now.size() < M) {
				M = now.size();
				all.clear();
			}
			if ((int)now.size() == M) {
				for (int x : now) {
					all.push_back(x);
				}
			}
		}
	}
	for (int x : all) {
		ans[x] = 1;
	}
	return ans;
}

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