Submission #1059558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059558		Gromp15	Keys (IOI21_keys)	C++17	9 / 100	659 ms	40036 KiB

keys

#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct dsu {
	vector<int> p, size, got;
	dsu(int n, const vector<int>& r) : p(n), size(n, 1), got(n) {
		iota(all(p), 0);
		for (int i = 0; i < n; i++) got[i] = 1 << r[i];
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	bool merge(int a, int b) {
		a = get(a), b = get(b);
		if (a == b) return 0;
		if (size[a] < size[b]) swap(a, b);
		size[a] += size[b], got[a] |= got[b], p[b] = a;
		return 1;
	}
	int val(int v) {
		return got[get(v)];
	}
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = sz(r), m = sz(u);
	vector<vector<ar<int, 2>>> adj(n);
	vector<vector<ar<int, 2>>> edges(30);
	for (int i = 0; i < m; i++) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
		edges[c[i]].push_back({u[i], v[i]});
	}
	set<int> vis;
	queue<int> q;
	for (int i = 0; i < 30; i++) {
		vis.insert(1 << i);
		q.push(1 << i);
	}
	int mn = 1e9;
	vector<int> ans(n);
	while (q.size()) {
		int col = q.front(); q.pop();
		dsu d(n, r);
		for (int i = 0; i < 30; i++) if (col >> i & 1) {
			for (auto [x, y] : edges[i]) {
				d.merge(x, y);
			}
		}
		int o = mn;
		bool F = 0;
		for (int i = 0; i < n; i++) if (i == d.get(i) && (d.val(i) & col) == d.val(i)) { 
			F = 1;
			ckmin(mn, d.size[i]);
		}
		if (mn < o) {
			for (int i = 0; i < n; i++) {
				ans[i] = (d.val(i) & col) == d.val(i) && d.size[d.get(i)] == mn;
			}
		}
		else if (mn == o) {
			for (int i = 0; i < n; i++) {
				ans[i] |= (d.val(i) & col) == d.val(i) && d.size[d.get(i)] == mn;
			}
		}
		if (!F) {
			for (int i = 0; i < n; i++) if (i == d.get(i) && !vis.count(d.val(i)) && d.size[d.get(i)] < mn) {
				vis.insert(d.val(i));
				q.push(d.val(i));
			}
		}
	}
	return ans;
}

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