Submission #587212

#	Time	Username	Problem	Language	Result	Execution time	Memory
587212		jakubd	Keys (IOI21_keys)	C++17	9 / 100	3083 ms	25880 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;

		vector<int> waiting(n);

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

			have[r[v]] = 1;

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

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

		p[i] = accumulate(done.begin(), done.end(), 0);
	}

	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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33