Submission #760552

#	Time	Username	Problem	Language	Result	Execution time	Memory
760552		dxz05	Keys (IOI21_keys)	C++17	37 / 100	3064 ms	44776 KiB

keys

#include "keys.h"
#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]].emplace_back(V[i], C[i]);
		g[V[i]].emplace_back(U[i], C[i]);
	}

	function<int(int)> bfs = [&](int v){
		vector<vector<int>> blocked(n);
		vector<bool> has(n, false);

		queue<int> q;
		vector<bool> used(n, false);
		q.push(v);
		used[v] = true;

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

			if (!has[r[v]]){
				has[r[v]] = true;
				for (int i : blocked[r[v]]){
					if (!used[i]){
						used[i] = true;
						q.push(i);
					}
				}
			}

			for (auto [u, c] : g[v]){
				if (used[u]) continue;
				if (has[c]){
					used[u] = true;
					q.push(u);
				} else {
					blocked[c].push_back(u);
				}
			}

		}

		return count(used.begin(), used.end(), true);
	};

	vector<int> ans(n, 0);
	for (int i = 0; i < n; i++){
		bool nowhere = true;
		for (auto [j, c] : g[i]){
			if (c == r[i]) nowhere = false;
		}
		if (nowhere) ans[i] = 1;
	}

	if (*max_element(ans.begin(), ans.end()) == 1) {
		return ans;
	}

	vector<int> p(n);
	int mn = n;
	for (int i = 0; i < n; i++){
		p[i] = bfs(i);
		mn = min(mn, p[i]);
	}

	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