Submission #1211656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211656		m5588ohammed	Keys (IOI21_keys)	C++20	37 / 100	772 ms	8772 KiB

keys

#include <bits/stdc++.h>
using namespace std;
vector <int> edges[2005],arr;
set <int> keys;
vector <array<int,2>> v[2005];
int n,m,vis[2005],cost[2005],cnt=0,mn=1e9;
void unlock(int i){
	cnt++;
	vis[i]=1;
	if(keys.find(arr[i])==keys.end()){
		keys.insert(arr[i]);
		for(int j:edges[arr[i]]) if(vis[j]==0) unlock(j);
	}
	for(auto [j,c]:v[i]){
		if(vis[j]==1) continue;
		if(keys.find(c)!=keys.end()) unlock(j);
		else{
			edges[c].push_back(j);
		}
	}
	return;
}
void bfs(int i){
	cnt=0;
	keys.clear();
	for(int i=0;i<n;i++){
		edges[i].clear();vis[i]=0;
	}
	unlock(i);
	cost[i]=cnt;
	mn=min(mn,cost[i]);
	return;
}
vector<int> find_reachable(vector<int> r, vector<int> b, vector<int> a,vector<int> c){
	vector <int> ans;
	n=r.size();m=a.size();
	arr=r;
	for(int i=0;i<m;i++){
		v[a[i]].push_back({b[i],c[i]});
		v[b[i]].push_back({a[i],c[i]});
	}
	for(int i=0;i<n;i++) bfs(i);
	for(int i=0;i<n;i++) {
		if(mn==cost[i]) ans.push_back(1);
		else ans.push_back(0);
	}
	return ans;
	return {};
}

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