Submission #437695

#	Time	Username	Problem	Language	Result	Execution time	Memory
437695		jeroenodb	Keys (IOI21_keys)	C++17	0 / 100	2 ms	460 KiB

keys

#include "bits/stdc++.h"
#include "keys.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int r){return std::uniform_int_distribution<int>(0,r-1)(rng);}

struct blockedges {
	vvi blocked;
	unordered_set<int> used;
	blockedges(int n) {
		blocked.resize(n);
	}
	void add(int r, int to) {
		if(blocked[r].empty()) used.insert(r);
		blocked[r].push_back(to);
	}
	void reset() {
		for(int i:used) blocked[i].clear();
		used.clear();
	}
};
vi find_reachable(vi r, vi u, vi v, vi c) {
	int n = r.size();
	vvi adj(n);
	int m=c.size();
	for(int i=0;i<m;++i) {
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	for(int i=0;i<n;++i) {
		random_shuffle(all(adj[i]),rnd);
	}
	vector<unordered_set<int>> sets(n);
	vi par(n,-1);
	vi order(n); iota(all(order),0);
	random_shuffle(all(order),rnd);
	vector<bool> done(n);
	int minimum=oo;
	blockedges bl(n);
	for(auto start : order) {
		bl.reset();
		// Simulate process
		stack<int> explore;
		unordered_set<int> keys;
		auto& vis = sets[start];
		explore.push(start);
		vis.insert(start);
		keys.insert(r[start]);

		while(!explore.empty()) {
			int at = explore.top(); explore.pop();
			vi& unblock = bl.blocked[r[at]];
			auto explorefurther = [&](int to) {
				if(!vis.count(to)) {
					if(done[to]) {
						if(sets[to].count(start)) {
							// stop simulating, exact same set, already simulated
							par[start] = par[to];
						} else par[start]=-2; // this set is strictly bigger than another, no point in simulating
						return;
					}
					vis.insert(to);
					explore.push(to);
					keys.insert(r[to]);
				}
			};
			while(!unblock.empty() and vis.size()<=minimum) {
				int to = unblock.back(); unblock.pop_back();
				explorefurther(to);
				if(par[at]!=-1 or vis.size()>minimum) break;
			}
			for(int eid : adj[at]) {
				int to = u[eid]^v[eid]^at;
				if(keys.count(c[eid])) {
					// already have key, explore directly
					explorefurther(to);
					if(par[at]!=-1 or vis.size()>minimum) break;
				} else if(!vis.count(to)) {
					// add to blocked vertices, vertices that have an edge to them, but we haven't got the key yet
					bl.add(c[eid],to);
				}
			}
		}
		if(par[start]==-1 and vis.size()<=minimum) {
			par[start]=start;
			minimum = vis.size();
		}
		if(par[start]==-1) par[start]=-2;
		done[start]=true;
	}
	vi ans(n,0);
	for(int i=0;i<n;++i) {
		if(par[i]>=0 and sets[par[i]].size()==minimum) ans[i]=1;
	}
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:79:41: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |    while(!unblock.empty() and vis.size()<=minimum) {
      |                               ~~~~~~~~~~^~~~~~~~~
keys.cpp:82:33: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     if(par[at]!=-1 or vis.size()>minimum) break;
      |                       ~~~~~~~~~~^~~~~~~~
keys.cpp:89:34: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |      if(par[at]!=-1 or vis.size()>minimum) break;
      |                        ~~~~~~~~~~^~~~~~~~
keys.cpp:96:35: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |   if(par[start]==-1 and vis.size()<=minimum) {
      |                         ~~~~~~~~~~^~~~~~~~~
keys.cpp:105:39: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |   if(par[i]>=0 and sets[par[i]].size()==minimum) ans[i]=1;
      |                    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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