Submission #1019835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019835		aufan	Keys (IOI21_keys)	C++17	37 / 100	3086 ms	29228 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<vector<pair<int, int>>> g(n);
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}

	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		vector<int> vis(n), done(n), q(1, i);
		vector<vector<int>> pend(n);
		vis[i] = 1;
		for (int j = 0; j < (int)q.size(); j++) {
			int x = q[j];

			if (!done[r[x]]) {
				done[r[x]] = 1;
				for (auto z : pend[r[x]]) {
					if (!vis[z]) {
						vis[z] = 1;
						q.push_back(z);
					}
				}
			}

			for (auto [z, y] : g[x]) {
				if (!done[y]) {
					pend[y].push_back(z);
				} else {
					if (!vis[z]) {
						vis[z] = 1;
						q.push_back(z);
					}
				}
			}
		}

		p[i] = count(vis.begin(), vis.end(), 1);
	}

	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