Submission #1220098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220098		jellybean	Keys (IOI21_keys)	C++20	20 / 100	59 ms	8264 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dl(x) cout<<#x<<" is "; for(auto i:x) cout<<i<<' '; cout<<endl;

typedef pair<int,int> pii;

vector<pii> adj[205];
int obtained[205]; //key
int unlocked[205]; //path
int vis[205]; //node
int numreached[205]; //node;

set<int>s;

void dfs(int x, vector<int> &r){
	for(auto [v,id]: adj[x]){
		if(!unlocked[id]) continue;
		if(vis[v]) continue;
		vis[v] = 1;
		if(!obtained[r[v]]) s.insert(r[v]);
		dfs(v,r);
	}
}

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(), m = c.size();
	vector<int> ans;
	
	for(int i=0; i<m; i++){
		int a = u[i], b = v[i];
		adj[a].pb({b,i});
		adj[b].pb({a,i});
	}
	
	for(int i=0; i<n; i++){
		s = set<int>();
		s.insert(r[i]);
		memset(obtained,0,sizeof(obtained));
		memset(unlocked,0,sizeof(unlocked));
		
		while(!s.empty()){
			for(auto key: s){
				obtained[key] = 1;
				for(int j=0; j<m; j++){
					if(c[j] == key) unlocked[j] = 1;
				}
			}
			s = set<int>();
			
			memset(vis,0,sizeof(vis));
			//dl(vis)
			vis[i] = 1;
			dfs(i,r);
		}
		
		
		for(int j=0; j<n; j++) if(vis[j]) numreached[i]++;
		
	}
	
	int x = *min_element(numreached, numreached+n);
	
	for(int i=0; i<n; i++) {
		if(numreached[i] == x) ans.pb(1);
		else ans.pb(0);
	}
	
	//for(int i=0; i<n; i++) cout<<numreached[i]<<' ';
	//cout<<endl;
	
	return ans;
}

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