oj.uz

Submission #837196

# Submission time Handle Problem Language Result Execution time Memory
837196 2023-08-25T07:55:31 Z QwertyPi Keys (IOI21_keys) C++17
0 / 100
 20 ms 42584 KB 
#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]){
		done[x] = true; _size[x] = 1 << 30;
		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);
	}
}

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);
		} 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;
				}
			}
		}
	}
	for(auto u : *nodes[v].vertexes){
		if(!done[u]) {
			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.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 20 ms 42580 KB Output is correct
4 Incorrect 20 ms 42580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 20 ms 42580 KB Output is correct
4 Incorrect 20 ms 42580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 20 ms 42580 KB Output is correct
4 Incorrect 20 ms 42580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 20 ms 42580 KB Output is correct
4 Incorrect 20 ms 42580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 19 ms 42584 KB Output is correct
3 Correct 20 ms 42580 KB Output is correct
4 Incorrect 20 ms 42580 KB Output isn't correct
5 Halted 0 ms 0 KB -