Submission #591033

#	Time	Username	Problem	Language	Result	Execution time	Memory
591033		Lucpp	Keys (IOI21_keys)	C++17	100 / 100	691 ms	58740 KiB

keys

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;

int n, maxC;
vector<int> par;
int find(int u){
	if(u == par[u]) return u;
	else return par[u] = find(par[u]);
}
void merge(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	par[b] = a;
}

vector<vector<pair<int, int>>> g;
vector<bool> vis, ok;
vector<int> ke;
vector<bool> keys;
vector<vector<int>> edges;

queue<int> q;
vector<int> visited;

int best = INF;
vector<int> good;
vector<bool> alive;

vector<int> undo_key, undo_edge;
void undo(){
	for(int i : undo_key) keys[i] = false;
	for(int i : undo_edge) edges[i].clear();
	undo_key.clear();
	undo_edge.clear();
	visited.clear();
	q = queue<int>();
}

bool visit(int u);

bool go(int u, int v){
	if(!alive[find(v)]) return true;
	if(find(v) != find(u)){
		merge(v, u);
		ok[find(v)] = true;
		return true;
	}
	if(!vis[v]){
		if(visit(v)) return true;
	}
	return false;
}

bool visit(int u){
	vis[u] = true;
	visited.push_back(u);
	q.push(u);
	if(!keys[ke[u]]){
		undo_key.push_back(ke[u]);
		keys[ke[u]] = true;
		for(int v : edges[ke[u]]){
			if(go(u, v)) return true;
		}
	}
	return false;
}

void bfs(int start){
	undo();
	q = queue<int>({start});
	keys[ke[start]] = true;
	undo_key.push_back(ke[start]);
	vis[start] = true;
	visited.push_back(start);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto [v, k] : g[u]){
			if(!keys[k]){
				undo_edge.push_back(k);
				edges[k].push_back(v);
			}
			else if(go(u, v)) return;
		}
	}
	int s = (int)visited.size();
	if(s < best) best = s, good.clear();
	if(s == best){
		for(int u : visited) good.push_back(u);
	}
	alive[start] = false;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	ke = r;
	n = (int)r.size();
	maxC = 0;
	for(int i : r) maxC = max(maxC, i);
	for(int i : c) maxC = max(maxC, i);
	maxC++;
	par.resize(n);
	for(int i = 0; i < n; i++) par[i] = i;
	g.resize(n);
	for(int i = 0; i < (int)u.size(); i++){
		g[u[i]].emplace_back(v[i], c[i]);
		g[v[i]].emplace_back(u[i], c[i]);
	}
	alive.assign(n, true);
	keys.assign(maxC, false);
	edges.resize(maxC);
	vector<int> comp(n);
	for(int i = 0; i < n; i++) comp[i] = i;
	while(!comp.empty()){
		vis.assign(n, false);
		ok.assign(n, false);
		for(int i : comp){
			if(!ok[i]) bfs(i);
		}
		comp.clear();
		for(int i = 0; i < n; i++) if(find(i) == i && ok[i]) comp.push_back(i);
	}
	vector<int> ans(n);
	for(int i : good) ans[i] = 1;
	return ans;
}

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