Submission #1173860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173860		anonymousbunny	Keys (IOI21_keys)	C++20	100 / 100	1205 ms	208480 KiB

keys

#include <bits/stdc++.h>
using namespace std;

#define maxn 300010

struct node{
	int id, sz, par, is_deactivated;
	vector <int> keys;
	vector <int> rooms;
	vector < pair<int,int> > edges; // pairs (key, room)
};

int print_flag;



vector <int> key_store[maxn], room_store[maxn];
vector < pair<int,int> > edge_store[maxn];
int sz[maxn], node_par[maxn], id[maxn];
int par[maxn], ans[maxn], is_deactivated[maxn];


int root (int v){
	if (v==par[v]) return v;
	return par[v]= root(par[v]);
}


void merge (int i, int j){
	i= root(i);
	j= root(j);
	if (i==j) return;
	if (sz[i]>sz[j]) {
		par[j]=i;
		for (int key:key_store[j]) key_store[i].push_back(key);
		for (pair <int,int> p:edge_store[j]) edge_store[i].push_back(p);
		for (int room:room_store[j]) room_store[i].push_back(room);	
		key_store[j].clear();
		edge_store[j].clear();
		room_store[j].clear();
		sz[i] += sz[j];

	}
	else{
		par[i]=j;
		for (int key:key_store[i]) key_store[j].push_back(key);
		for (pair<int, int> p:edge_store[i]) edge_store[j].push_back(p);
		for (int room:room_store[i]) room_store[j].push_back(room);
		key_store[i].clear();
		edge_store[i].clear();
		room_store[i].clear();
		sz[j] += sz[i];
	}
}

vector <int> adj[maxn], rev_adj[maxn], extended_adj[maxn];
int key_is_available[maxn];
void add_edges (int n){
	for (int i=1; i<=n; i++) {
		adj[i].clear();
		extended_adj[i].clear();
		rev_adj[i].clear();
	}

	for (int i=1; i<=n; i++){
		if (i!=root(i) or is_deactivated[i]) continue;
		for (int key:key_store[i]) key_is_available[key]=1;

		for (pair <int,int> p:edge_store[i]){
			int key= p.first, room= p.second;
			room= root(room);
			if (i==room) continue;
			if (key_is_available[key]) {
				extended_adj[i].push_back(room);
				if (is_deactivated[room]==0) adj[i].push_back(room);
				rev_adj[room].push_back(i);
			}

		}
		for (int key:key_store[i]) key_is_available[key]=0;
	}	
}

vector <int> terminals;

int vis[maxn];

void rev_dfs (int v){
	vis[v]=1;
	is_deactivated[v]=1;
	for (int u:rev_adj[v]) if (!vis[u]) rev_dfs(u);
}

void deactivate_bad_nodes (int n){
	terminals.clear();
	for (int i=1; i<=n; i++) vis[i]=0; 
	for (int i=1; i<=n; i++) {
		if (i==root(i)){
			if (is_deactivated[i]==1) rev_dfs(i);
			else{
				if (extended_adj[i].size()==0){
					is_deactivated[i]=1;
					for (int room:room_store[i]) ans[room]= sz[i];

					rev_dfs(i);
				}
			}
		}
	}
}


int scc_par[maxn], scc_visited[maxn];


vector <int> ordering;

int bad_count=0;
void scc_dfs (int v){
	scc_visited[v]=1;
	bad_count++;
	//cout<<"bad count "<<bad_count<<endl;
//	cout<<v<<" "<<"NEXT "<<endl;
	//for (int u:adj[v]) cout<<u<<" ";
//	cout<<endl;	
	for (int u:adj[v]){
		if (!scc_visited[u]) {
			scc_dfs(u);
		}
	}
	ordering.push_back(v);

}

void scc_rev_dfs (int v, int p){
	scc_par[v]=p;
	for (int u:rev_adj[v]){
		if (scc_par[u]==0) scc_rev_dfs(u, p);
	}
}

vector <int> compressed_dag_edges[maxn];

int terminal_children[maxn][2];

int done_collecting_information[maxn];
void collect_information (int v){
	done_collecting_information[v]=1;
	if (compressed_dag_edges[v].empty()){
		terminal_children[v][0]= v;
		terminal_children[v][1]= -1;

	}

	else{
		vector <int> reachable_terminals;
		for (int w:compressed_dag_edges[v]){
			if (!done_collecting_information[w]) collect_information(w);
			if (terminal_children[w][0]!=-1 and reachable_terminals.size()<2) reachable_terminals.push_back(terminal_children[w][0]);
			if (terminal_children[w][1]!=-1 and reachable_terminals.size()<2) reachable_terminals.push_back(terminal_children[w][1]); 
		}
		if (reachable_terminals.size()>=2){
			terminal_children[v][0]= reachable_terminals[0];
			terminal_children[v][1]= reachable_terminals[1];
		}
		if (reachable_terminals.size()==1){
			terminal_children[v][0]= reachable_terminals[0];
			terminal_children[v][1]= -1;
		}
	}
}

int check_if_valid (int v, int terminal_id){
	v= scc_par[v];

	if (terminal_children[v][0]==terminal_id and terminal_children[v][1]==-1) return 1;
	if (terminal_children[v][1]==terminal_id and terminal_children[v][0]==-1) return 1;
	return 0;
}

vector <int> expanded_sccs[maxn];
vector <int> store_scc[maxn];

int done_scc[maxn];

void find_sccs (int n){
	ordering.clear();
	for (int i=1; i<=n; i++){
		scc_par[i]=0;
		scc_visited[i]=0;
		done_collecting_information[i]=0;
		done_scc[i]=0;
		store_scc[i].clear();
		compressed_dag_edges[i].clear();
		terminal_children[i][0]= -1;
		terminal_children[i][1]=-1;
	}
	for (int i=1; i<=n; i++){
		if (i==root(i) and !is_deactivated[i] and !scc_visited[i]) {
		//	cout<<"visiting "<<i<<endl;
			scc_dfs(i);
		}
	}
	reverse(ordering.begin(), ordering.end());
	for (int u:ordering) if (scc_par[u]==0) scc_rev_dfs(u, u);
	for (int i=1; i<=n; i++){
		if (scc_par[i]!=0 and i==root(i) and !is_deactivated[i]) store_scc[scc_par[i]].push_back(i); 
	}	
	
	for (int i=1; i<=n; i++){
		if (i==root(i) and !is_deactivated[i]){
			for (int v:adj[i]){
				if (scc_par[v]!=scc_par[i]) {
					int comp_i= scc_par[i], comp_v= scc_par[v];
					compressed_dag_edges[comp_i].push_back(comp_v);
				}
			}
		}
	}


	for (int i=1; i<=n; i++){
		if (i==root(i) and !is_deactivated[i] and i==scc_par[i] and !done_collecting_information[i]) collect_information(i);
	}



}


int expansion_is_key_available[maxn], expansion_is_vertex_visited[maxn];
vector <int > edges_by_key[maxn];

vector <int> list_of_vertices, list_of_keys;

void expansion_process_vertex (int v, int terminal_id){
	for (int key:key_store[v]) {
		if (!expansion_is_key_available[key]) {
			list_of_keys.push_back(key);
			expansion_is_key_available[key]=1;
			for (int other_vertex:edges_by_key[key]){

				if (!expansion_is_vertex_visited[other_vertex]) {
					list_of_vertices.push_back(other_vertex);
					expansion_is_vertex_visited[other_vertex]=1;
				}
			}
			edges_by_key[key].clear();
		}
	}

	for (pair<int,int> p:edge_store[v]){
		int key= p.first, room= p.second;
		room= root(room);
		if (key_is_available[key]){
			if (!expansion_is_vertex_visited[room] and check_if_valid(room, terminal_id)){
				expansion_is_vertex_visited[room]=1;
				list_of_vertices.push_back(room);
			}
		}
		else{
			if (!expansion_is_vertex_visited[room] and check_if_valid(room, terminal_id)) edges_by_key[key].push_back(room);
		}
	}



}

void expand_terminal (int terminal_id){
	if (terminal_id!=root(terminal_id) or terminal_id!=scc_par[terminal_id] or is_deactivated[terminal_id]) return;
//	if (terminal_id>=100000) cout<<"Expanding "<<terminal_id<<endl;

	expanded_sccs[terminal_id].push_back(terminal_id);
	if (compressed_dag_edges[terminal_id].size()>0) return;

	for (int vertex:store_scc[terminal_id]){
		if (expansion_is_vertex_visited[vertex]) continue;

		list_of_vertices.push_back(vertex);
		expansion_is_vertex_visited[vertex]=1;
		for (int key:key_store[vertex]) {
			if (expansion_is_key_available[key]==1) continue;
			list_of_keys.push_back(key);	
			expansion_is_key_available[key]=1;
		}
	}

	for (int i=0; i<(int) list_of_vertices.size(); i++){
		int cur_vertex= list_of_vertices[i];
		expansion_process_vertex(cur_vertex, terminal_id);
	}
	for (int vertex:list_of_vertices) expanded_sccs[terminal_id].push_back(scc_par[vertex]);

	for (int key:list_of_keys) {
		expansion_is_key_available[key]=0;
		edges_by_key[key].clear();
	}
	for (int vertex:list_of_vertices) expansion_is_vertex_visited[vertex]=0;
	list_of_vertices.clear();
	list_of_keys.clear();	
//	if (terminal_id==100000) cout<<"Expansion done "<<terminal_id<<endl;


}	



void process_sccs (int n){
	for (int i=1; i<=n; i++) done_scc[i]=0;
	for (int i=1; i<=n; i++) expanded_sccs[i].clear();
//	cout<<"Starting expansion "<<endl;	
	for (int i=1; i<=n; i++) expand_terminal(i);
//	cout<<"Expansion ended "<<endl;
		

	for (int i=1; i<=n; i++){
		if (expanded_sccs[i].size()>0){
			int representative_scc=expanded_sccs[i][0];
			int representative_vertex= store_scc[representative_scc][0];
			for (int scc:expanded_sccs[i]){
				if (done_scc[scc]) continue;
				done_scc[scc]=1;
				for (int vertex:store_scc[scc]) merge(representative_vertex, vertex);
			}
		}
	}	

}


void process_one_round(int n){
	add_edges(n);
	find_sccs(n);
	process_sccs(n);
	add_edges(n);
	deactivate_bad_nodes(n);



}

void init(int n){
	for (int i=1; i<=n; i++){
		par[i]=i;
		sz[i]=1;
		ans[i]= -1;
		key_store[i].clear();
		room_store[i].clear();
		room_store[i].push_back(i);
		edge_store[i].clear();
		expanded_sccs[i].clear();
		store_scc[i].clear();
		compressed_dag_edges[i].clear();
		is_deactivated[i]=0;
	}
}

vector <int> get_answer(int n){

	print_flag=1;
	for (int i=1; i<=20; i++) {
	//	cout<<"round "<<i<<endl;
		process_one_round(n);

		if (i>1) print_flag=0;
	}
	int mn_ans = n;	
	for (int i=1; i<=n; i++){
		if (ans[i]!=-1) mn_ans= min(mn_ans, ans[i]);
	}	
	vector <int> output;
	for (int i=1; i<=n; i++) {
		if (mn_ans==ans[i]) output.push_back(1);
		else output.push_back(0);
	}

	return output;

}


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c){
	int n= r.size();
	init(n);
	for (int i=1; i<=n; i++){
		key_store[i].push_back(r[i-1]+1);
	}

	for (int ed=0; ed<(int) u.size(); ed++){
		int endpoint_1= u[ed]+1, endpoint_2= v[ed]+1, key= c[ed]+1;
		edge_store[endpoint_1].push_back(make_pair(key, endpoint_2));
		edge_store[endpoint_2].push_back(make_pair(key, endpoint_1));
	}

	return get_answer(n);


}

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