Submission #1021445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021445		Wael	Keys (IOI21_keys)	C++17	37 / 100	3048 ms	21564 KiB

keys

#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

struct DSU {
	int n, cnt;
	vector<int> f, sz;
	vector<vector<int>> keys;
	DSU(int n, vector<int> r) : n(n), cnt(n) {
		f.resize(n);
		iota(f.begin(), f.end(), 0);
		sz.resize(n, 1);
		keys.resize(n);
		for (int i = 0; i < n; ++i) {
			keys[i].push_back(r[i]);
		}
	}

	int find(int u) {
		if (f[u] == u) return u;
		return f[u] = find(f[u]);
	}

	void merge(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) return;
		--cnt;
		if (sz[v] > sz[u]) {
			swap(u, v);
		}
		f[v] = u;
		sz[u] += sz[v];
		for (auto k : keys[v]) {
			keys[u].push_back(k);
		}
		vector<int>().swap(keys[v]);
	}

	bool same(int u, int v) {
		return find(u) == find(v);
	}
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();

	vector<vector<int>> edges(n);
	for (int j = 0; j < m; ++j) {
		edges[c[j]].push_back(j);
	}

	vector<int> p(n);
	for (int i = 0; i < n; ++i) {
		DSU dsu(n, r);

		vector<int> vis(n);
		vector<int> have;
		have.push_back(r[i]);
		while (have.size()) {
			int k = have.back();
			have.pop_back();
			if (vis[k]) {
				continue;
			}
			vis[k] = 1;
			for (auto j : edges[k]) {
				auto [x, y] = make_pair(u[j], v[j]);
				if (dsu.same(x, y)) {
					continue;
				}
				if (dsu.same(i, y)) {
					swap(x, y);
				}
				if (dsu.same(i, x)) {
					for (auto z : dsu.keys[dsu.find(y)]) {
						have.push_back(z);
					}
				}
				dsu.merge(x, y);
			}
		}

		p[i] = dsu.sz[dsu.find(i)];
	}

	int mn = *min_element(p.begin(), p.end());
	vector<int> 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