Submission #1245090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245090		nicolo_010	Keys (IOI21_keys)	C++20	20 / 100	3088 ms	14020 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
using ll = long long;
#define rep(i, k, n) for (int i=k;i<n;i++)

struct DSU {
	vector<int> rank, parent;
	vector<int> contain;
	DSU(int n, int i) {
		rank.assign(n, 1);
		parent.resize(n);
		contain.assign(n, 0);
		contain[i] = 1;
		rep(i, 0, n) parent[i] = i;
	}

	int find(int n) {
		return (parent[n] == n ? n : parent[n] = find(parent[n]));
	}

	bool unite(int n1, int n2) {
		int p1 = find(n1), p2 = find(n2);
		if (p1 == p2) return false;
		if (rank[p1] > rank[p2]) {
			rank[p1] += rank[p2];
			parent[p2] = p1;
			contain[p1] |= contain[p2];
		}
		else {
			rank[p2] += rank[p1];
			parent[p1] = p2;
			contain[p2] |= contain[p1];
		}
		return true;
	}
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = v.size();
	vector<int> ans(n);
	vector<int> sz(n, 1);
	vector<vector<int>> edges(n);
	rep(i, 0, m) {
		edges[c[i]].push_back(i);
	}
	rep(i, 0, n) {
		DSU dsu(n, i);
		vector<bool> vis(n, false);
		queue<int> q;
		q.push(r[i]);
		vis[r[i]] = true;
		while (!q.empty()) {
			int color = q.front();
			q.pop();
			for (auto x : edges[color]) {
				int n1 = u[x], n2 = v[x];
				dsu.unite(n1, n2);
				int p1 = dsu.find(n1), p2 = dsu.find(n2);
				if (dsu.contain[p1] || dsu.contain[p2]) {
					if (!vis[r[n1]]) {
						vis[r[n1]] = true;
						q.push(r[n1]);
					}
					if (!vis[r[n2]]) {
						vis[r[n2]] = true;
						q.push(r[n2]);
					}
				} 
			}
		}
		int pi = dsu.find(i);
		sz[i] = dsu.rank[pi];
	}
	int mn = 1e9;
	rep(i, 0, n) mn = min(mn, sz[i]);
	rep(i, 0,  n) {
		if (sz[i] <= mn) ans[i] = 1;
		else ans[i] = 0;
	}
	return ans;
}

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