Submission #837282

#	Time	Username	Problem	Language	Result	Execution time	Memory
837282		QwertyPi	Keys (IOI21_keys)	C++17	100 / 100	1615 ms	146824 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 3e5 + 11;

struct edge{
	int to, c;
	bool operator< (const edge& o) const {
		return c < o.c || (c == o.c && to < o.to);
	}
};

set<int> _vertexes[N_MAX];
set<int> _keys[N_MAX];
set<edge> _edges[N_MAX];
set<edge> _ok_edges[N_MAX];

struct node{
	set<int>* vertexes;
	set<int>* keys;
	set<edge>* edges;
	set<edge>* ok_edges;
	int find_next();
	void clear();
} nodes[N_MAX];

int prv[N_MAX], _size[N_MAX];
bool vis[N_MAX], done[N_MAX];

void fill_none(int v){
	int x = v;
	while(!done[x]){
		for(auto y : *nodes[x].vertexes){
			done[y] = true; _size[y] = 1 << 30;
		}
		nodes[x].clear();
		x = prv[x];
	}
}

int back_number = -1;

void node::clear(){
	vertexes->clear();
	keys->clear();
	edges->clear();
}

int node::find_next(){
	while(ok_edges->size()){
		int u = ok_edges->begin()->to;
		ok_edges->erase(ok_edges->begin());
		if(!vertexes->count(u)) return u;
	}
	return -1;
}

void merge(int u, int v){
	// OK Edges
	if(nodes[u].ok_edges->size() < nodes[v].ok_edges->size()){
		swap(nodes[u].ok_edges, nodes[v].ok_edges);
	}
	for(auto e : *nodes[v].ok_edges){
		nodes[u].ok_edges->insert(e);
	}

	// Edges
	if(nodes[u].edges->size() + nodes[u].keys->size() < nodes[v].keys->size() + nodes[v].keys->size()){
		swap(nodes[u].edges, nodes[v].edges);
		swap(nodes[u].keys, nodes[v].keys);
	}
	for(auto x : *nodes[v].keys){
		auto ptr = nodes[u].edges->lower_bound({-1, x});
		while(ptr != nodes[u].edges->end() && ptr->c == x){
			nodes[u].ok_edges->insert({ptr->to, ptr->c});
			nodes[u].edges->erase(ptr);
			ptr = nodes[u].edges->lower_bound({-1, x});
		}
	}
	for(auto [to, x] : *nodes[v].edges){
		if(nodes[u].keys->count(x)){
			nodes[u].ok_edges->insert({to, x});
		}else{
			nodes[u].edges->insert({to, x});
		}
	}

	// Vertexes
	if(nodes[u].vertexes->size() < nodes[v].vertexes->size()){
		swap(nodes[u].vertexes, nodes[v].vertexes);
	}
	for(auto x : *nodes[v].vertexes){
		nodes[u].vertexes->insert(x);
	}

	// Keys
	if(nodes[u].keys->size() < nodes[v].keys->size()){
		swap(nodes[u].keys, nodes[v].keys);
	}
	for(auto x : *nodes[v].keys){
		nodes[u].keys->insert(x);
	}

	nodes[v].clear();
}

void dfs(int v, int pa = -1){
	vis[v] = true;
	while(true){
		int u = nodes[v].find_next();
		if(u == -1) break;
		if(done[u]) {
			fill_none(v);
			return;
		} else if(vis[u]) {
			back_number = u;
			merge(prv[v], v);
			return;
		} else {
			prv[u] = v; dfs(u, v);
			if(back_number != -1){
				if(nodes[v].vertexes->count(back_number)){
					back_number = -1;
				}else{
					merge(prv[v], v);
					return;
				}
			}
			if(done[v]) return;
		}
	}
	for(auto u : *nodes[v].vertexes){
		done[u] = true; _size[u] = nodes[v].vertexes->size();
	}
	fill_none(prv[v]);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size(), m = u.size();
	vector<int> ans(n);
	
	for(int i = 0; i < n; i++){
		nodes[i].vertexes = &_vertexes[i];
		nodes[i].keys = &_keys[i];
		nodes[i].edges = &_edges[i];
		nodes[i].ok_edges = &_ok_edges[i];
	}

	for(int i = 0; i < n; i++) nodes[i].vertexes->insert(i);
	for(int i = 0; i < n; i++) nodes[i].keys->insert(r[i]);
	for(int i = 0; i < m; i++) {
		if(r[u[i]] == c[i]) nodes[u[i]].ok_edges->insert({v[i], c[i]});
		else nodes[u[i]].edges->insert({v[i], c[i]});

		if(r[v[i]] == c[i]) nodes[v[i]].ok_edges->insert({u[i], c[i]});
		else nodes[v[i]].edges->insert({u[i], c[i]});
	}

	for(int i = 0; i < n; i++){
		if(!vis[i]){
			dfs(i);
		}
	}
	for(int i = 0; i < n; i++) assert(done[i]);
	
	int min_size = *min_element(_size, _size + n);
	for(int i = 0; i < n; i++){
		ans[i] = _size[i] == min_size;
	}
	return ans;
}

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