Submission #623038

#	Time	Username	Problem	Language	Result	Execution time	Memory
623038		Temmie	Keys (IOI21_keys)	C++17	37 / 100	3064 ms	50712 KiB

keys

#include <bits/stdc++.h>

struct Dsu {
	
	std::vector <int> p;
	std::vector <int> size;
	
	Dsu(int s) {
		p.resize(s);
		std::iota(p.begin(), p.end(), 0);
		size.resize(s, 1);
	}
	
	int find(int v) {
		return v == p[v] ? v : (p[v] = find(p[v]));
	}
	
	void unite(int u, int v) {
		if ((u = find(u)) == (v = find(v))) {
			return;
		}
		if (size[u] > size[v]) {
			p[v] = u;
		} else {
			p[u] = v;
		}
	}
	
};

struct Edge {
	
	int u, v, c;
	
};

int n, m;
std::vector <Edge> ed;
std::vector <std::vector <int>> g;
std::vector <int> p;
Dsu dsu(0), tree(0);
std::vector <int> r;

bool go() {
	std::vector <std::unordered_set <int>> keys(n);
	for (int i = 0; i < n; i++) {
		keys[dsu.find(i)].insert(r[i]);
	}
	std::vector <std::vector <int>> eds(n);
	for (int i = 0; i < n; i++) {
		for (int x : g[i]) {
			if (keys[dsu.find(i)].count(ed[x].c)) {
				eds[dsu.find(i)].push_back(ed[x].u ^ ed[x].v ^ i);
			}
		}
	}
	bool did = false;
	for (int i = 0; i < n; i++) {
		int v = dsu.find(i);
		if (p[v] != -1) {
			continue;
		}
		for (int x : eds[v]) {
			if (dsu.find(x) == v) {
				continue;
			}
			did = true;
			if (tree.find(x) == tree.find(v)) {
				int to = dsu.find(x);
				while (v != to) {
					int new_to = dsu.find(p[to]);
					p[v] = p[to] = p[v];
					dsu.unite(to, v);
					to = new_to;
				}
			} else {
				p[v] = dsu.find(x);
				tree.unite(x, v);
				break;
			}
		}
	}
	return did;
}

std::vector <int> find_reachable(std::vector <int> _r, std::vector <int> u, std::vector <int> v, std::vector <int> c) {
	r = _r;
	n = r.size();
	m = c.size();
	ed.resize(m);
	g.resize(n);
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
		ed[i] = { u[i], v[i], c[i] };
	}
	p.resize(n, -1);
	dsu = Dsu(n);
	tree = Dsu(n);
	while (go());
	std::vector <int> ans(n, 0);
	for (int i = 0; i < n; i++) {
		ans[dsu.find(i)] += p[dsu.find(i)] == -1;
	}
	int res = 1 << 30;
	for (int x : ans) {
		if (x) {
			res = std::min(res, x);
		}
	}
	std::vector <int> ret(n, 0);
	for (int i = 0; i < n; i++) {
		if (ans[dsu.find(i)] == res) {
			ret[i] = 1;
		}
	}
	return ret;
}

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