Submission #816946

#	Time	Username	Problem	Language	Result	Execution time	Memory
816946		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	704 ms	39904 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"

using namespace std;

#define all(x) x.begin(), x.end()

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	vector<int> ans(n);
	vector<pair<int, int>> g[n + 2];
	for (int i = 0; i < u.size(); i++) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
	int mn = n + 10;
	for (int i = 0; i < n; i++) {
		deque<int> dq;
		unordered_set<int> got, visited;
		dq.push_front(i);
		bool bigger = 0;
		while (dq.size()) {
			int fr = dq.front();
			if (fr < i && ans[fr] > mn) {
				bigger = 1;
				break;
			}
			dq.pop_front();
			bool been = visited.count(fr); 
			visited.insert(fr);
			if (visited.size() > mn) break;
			got.insert(r[fr]);
			bool unvisited = 0;
			for (auto x : g[fr]) {
				if (visited.count(x.first)) continue;
				if (!got.count(x.second)) {
					unvisited = 1;
					continue;
				}
				visited.insert(x.first);
				got.insert(r[x.first]);
				dq.push_front(x.first);
			}
			if (unvisited && !been) dq.push_back(fr);
		}
		int sz = visited.size();
		if (bigger) sz = mn + 5;
		mn = min(mn, sz);
		ans[i] = sz;
	}
	vector<int> ret;
	for (int i = 0; i < n; i++) ret.push_back(ans[i] == mn);
	return ret;
}

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:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~
keys.cpp:31:23: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |    if (visited.size() > mn) break;
      |        ~~~~~~~~~~~~~~~^~~~

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