Submission #837203

#	Time	Username	Problem	Language	Result	Execution time	Memory
837203		QwertyPi	Keys (IOI21_keys)	C++17	0 / 100	19 ms	42580 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];

struct node{
	set<int>* vertexes;
	set<int>* keys;
	set<edge>* 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[v];
	}
}

int back_number = -1;

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

int node::find_next(){
	for(auto [u, c] : *edges){
		if(keys->count(c) && !vertexes->count(u)){
			edges->erase({u, c});
			return u;
		}
	}
	return -1;
}

void merge(int u, int v){
	for(auto x : *nodes[v].vertexes){
		nodes[u].vertexes->insert(x);
	}
	for(auto x : *nodes[v].keys){
		nodes[u].keys->insert(x);
	}
	for(auto e : *nodes[v].edges){
		nodes[u].edges->insert(e);
	}
	nodes[v].clear();
}

void dfs(int v, int pa = -1){
	vis[v] = true;
	while(true){
		int u = nodes[v].find_next();
		// printf("node %d -> node %d\n", v, u);
		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(v == 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];
	}

	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++) {
		nodes[u[i]].edges->insert({v[i], c[i]});
		nodes[v[i]].edges->insert({u[i], c[i]});
	}

	for(int i = 0; i < n; i++){
		if(!vis[i]){
			dfs(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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33