Submission #623406

#	Time	Username	Problem	Language	Result	Execution time	Memory
623406		cheissmart	Keys (IOI21_keys)	C++17	37 / 100	3073 ms	38760 KiB

keys

#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 3e5 + 7;

V<pi> G[N];
vi aux[N];
queue<int> q;
bool dead[N], vis[N];

vi find_reachable(vi r, vi _u, vi _v, vi c) {
	int n = SZ(r), m = SZ(_u);

	for(int i = 0; i < m; i++) {
		int u = _u[i], v = _v[i];
		G[u].EB(v, c[i]);
		G[v].EB(u, c[i]);
	}

	vi p(n);

	auto solve = [&] (int s) {
		q.push(s);
		auto kill = [&] (int color) {
			if(dead[color]) return;
			dead[color] = true;
			for(int e:aux[color]) q.push(e);
			aux[color].clear();
		};
		auto add = [&] (int color, int v) {
			if(dead[color]) q.push(v);
			else aux[color].PB(v);
		};
		int ans = 0;
		while(q.size()) {
			int u = q.front(); q.pop();
			if(vis[u]) continue;
			vis[u] = true;
			ans++;
			kill(r[u]);
			for(auto[v, c]:G[u])
				add(c, v);
		}
		q = queue<int>();
		for(int i = 0; i < n; i++) {
			aux[i].clear();
			dead[i] = false;
			vis[i] = false;
		}
		return ans;
	};

	for(int i = 0; i < n; i++) {
		p[i] = solve(i);
	}

	int mn = *min_element(ALL(p));
	vi 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: 0 / 30
• Subtask 5: 0 / 33