Submission #894375

#	Time	Username	Problem	Language	Result	Execution time	Memory
894375		Trisanu_Das	Keys (IOI21_keys)	C++17	37 / 100	3040 ms	23260 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 = r.size();
	vector<pair<int, int>> adj[n];
	for (int i = 0; i < U.size(); i++) {
		adj[U[i]].push_back({V[i], C[i]});
		adj[V[i]].push_back({U[i], C[i]});
	}
	vector<int> cnt(n);
	for (int i = 0; i < n; i++) {
		vector<bool> has(n), vis(n);
		queue<int> q;
		q.push(i);
		vis[i] = true;
		vector<int> nodes[n];
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int v : nodes[r[u]]) {
				if (!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
			has[r[u]] = true;
			for (auto [v, c] : adj[u]) {
				if (vis[v]) continue;
				if (has[c]) {
					vis[v] = true;
					q.push(v);
				} else nodes[c].push_back(v);
			}
		}
		for (int j : vis) cnt[i] += j;
	}
	vector<int> ans(n);
	int mn = *min_element(cnt.begin(), cnt.end());
	for (int i = 0; i < n; i++) ans[i] = (cnt[i] == mn);
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:6:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |  for (int i = 0; i < U.size(); i++) {
      |                  ~~^~~~~~~~~~

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