Submission #816963

#	Time	Username	Problem	Language	Result	Execution time	Memory
816963		vjudge1	Keys (IOI21_keys)	C++17	0 / 100	0 ms	212 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), res(n);
	vector<pair<int, int>> g[n + 2];
	set<int> comp;
	for (int i = 0; i < u.size(); i++) {
		comp.insert(c[i]);
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
	int cnt = 0;
	unordered_map<int, int> h;
	for (auto x : comp) h[x] = cnt++;
	int mn = n;
	for (int i = 0; i < n; i++) {
		deque<int> dq;
		unordered_set<int> visited;
		dq.push_front(i);
		long long mask = 0;
		if (h.count(r[i])) mask = (1 << h[r[i]]); 
		while (dq.size() && visited.size() <= mn) {
			int fr = dq.front();
			dq.pop_front();
			bool been = visited.count(fr); 
			visited.insert(fr);
			bool unvisited = 0;
			for (auto x : g[fr]) {
				if (visited.count(x.first)) continue;
				if (!(mask & (1 << h[x.second]))) {
					unvisited = 1;
					continue;
				}
				visited.insert(x.first);
				if (h.count(r[x.first])) mask |= (1 << h[r[x.first]]);
				dq.push_front(x.first);
			}
			if (unvisited && !been) dq.push_back(fr);
		}
		mn = min(mn, (int) visited.size());
		ans[i] = visited.size(); 		
		cout << i << " " << mask << endl;
	}
	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:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~
keys.cpp:28:38: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   while (dq.size() && visited.size() <= mn) {
      |                       ~~~~~~~~~~~~~~~^~~~~

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