Submission #587226

#	Time	Username	Problem	Language	Result	Execution time	Memory
587226		jakubd	Keys (IOI21_keys)	C++17	37 / 100	3059 ms	26856 KiB

keys

	#include <bits/stdc++.h>

	using namespace std;

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

		vector<vector<pair<int, int>>> graph(n);

		for (int i = 0; i < m; i++) {
			graph[u[i]].push_back({v[i], c[i]});
			graph[v[i]].push_back({u[i], c[i]});
		}

		vector<int> p(n, n + 1);

		for (int i = 0; i < n; i++) {
			vector<int> have(n);

			queue<int> q; q.push(i);
			vector<int> done(n); done[i] = 1;

			map<int, set<int>> by_key;
			vector<int> waiting(n);

			while (!q.empty()) {
				int v = q.front(); q.pop();

				if (!have[r[v]]) {
					have[r[v]] = 1;

					for (int u : by_key[r[v]]) {
						if (!done[u]) {
							q.push(u);
							done[u] = 1;
						}
					}

					by_key.erase(r[v]);
				}

				for (auto e : graph[v]) {
					int u = e.first, req = e.second;

					if (done[u]) continue;
					
					if (!have[req]) {
						waiting[u] = 1;
						if (!by_key[req].count(u)) by_key[req].insert(u);
					} else {
						done[u] = 1;
						waiting[u] = 0;
						q.push(u);
					}
				}
			}

			p[i] = accumulate(done.begin(), done.end(), 0);
			// cout << p[i] << " ";
		}
		// cout << " p[i]\n";

		int mn = *min_element(p.begin(), p.end());

		for (int i = 0; i < n; i++) {
			if (p[i] != mn) {
				ans[i] = 0;
			}
		}

		return ans;
	}

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