Submission #437712

#	Time	Username	Problem	Language	Result	Execution time	Memory
437712		jeroenodb	Keys (IOI21_keys)	C++17	37 / 100	2561 ms	33172 KiB

keys

#include "bits/stdc++.h"
#include "keys.h"
// #pragma GCC optimize "Ofast"
// #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#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;
	vector<bool> used;
	vi res;
	blockedges(int n) {		
		blocked.resize(n), used.resize(n), res.reserve(n);
	}
	void add(int r, int to) {
		if(!used[r]) res.push_back(r);
		used[r] = true; 
		blocked[r].push_back(to);
	}
	void reset() {
		for(int i:res) blocked[i].clear(), used[i]=false;
	}
};
struct el {
	int at;
	vi::iterator it;
};
template<typename T> struct mystack {
	vector<T> st;
	int p=0;
	mystack(int n) {st.resize(n);}
	bool empty() {return p==0;}
	void push(T v) {
		st[p++]=v;
	}
	void pop() {p--;}
	T& top() {
		return st[p-1];
	}
	void clear() {p=0;}
};
vi find_reachable(vi r, vi u, vi v, vi c) {
	int n = r.size();
	vvi adj(n);
	int m=u.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);
	vector<bool> done(n);
	int minimum=oo;
	blockedges bl(n);
	vi order;
	{
		// generate random ordering based on degree of nodes
		vi sharr; sharr.reserve(2*m);
		for(int i=0;i<n;++i) {
			for(int j=0;j<max(1,(int)adj[i].size());++j) {
				sharr.push_back(i);
				if(adj[i].size()>7000) sharr.push_back(i);
			}
		}
		random_shuffle(all(sharr),rnd);
		vector<bool> used(n);
		for(int i:sharr) {
			if(!used[i]) order.push_back(i);
			used[i]=true;
		}
	}

	mystack<int> explore(n);
	mystack<el> extend(n);
	for(auto start : order) {
		bl.reset();
		explore.clear();
		extend.clear();
		unordered_set<int> keys;
		auto& vis = sets[start];
		// Simulate process
		auto add = [&](int to) {
			if(!vis.count(to)) {
				if(done[to]) {
					if(par[to]==-2) par[start]=-2;
					else if(sets[par[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);
				keys.insert(r[to]);
				explore.push(to);
				extend.push({to, adj[to].begin()});
			}
		};
		auto floodfill = [&]()  {
			while(!explore.empty()) {
				int at = explore.top(); explore.pop();
				vi& unblock = bl.blocked[r[at]];
				while(!unblock.empty()) {
					int to = unblock.back(); unblock.pop_back();
					add(to);
					if(par[start]!=-1 or (int)vis.size()>minimum) break;
				}
				if(par[start]!=-1 or (int)vis.size()>minimum) break;
			}
		};
		add(start);
		floodfill();
		while(par[start]==-1 and (int)vis.size()<=minimum and !extend.empty()) {
			auto& cur = extend.top();
			if(cur.it==adj[cur.at].end()) {
				extend.pop();
				continue;
			}
			int eid = *cur.it;
			int to = u[eid]^v[eid]^cur.at;
			if(keys.count(c[eid])) {
				// already have key, explore directly
				add(to);
				floodfill();
			} 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);
			}
			cur.it++;
		}
		if(par[start]==-1) {
			// finished whole simulation
			par[start]=start;
			minimum = min(minimum,(int)vis.size());
		}
		done[start]=true;
	}
	vi ans(n,0);
	for(int i=0;i<n;++i) {
		if(par[i]>=0 and (int)sets[par[i]].size()==minimum) ans[i]=1;
	}
	return ans;
}

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