Submission #1229031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229031		Ludissey	Keys (IOI21_keys)	C++20	37 / 100	3095 ms	30528 KiB

keys

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(a) (a.begin(), a.end())
#define sz(a) (int)a.size()


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size(), 1);
	int n=sz(r);
	vector<vector<pair<int,int>>> neigh(n);
	for (int i = 0; i < sz(u); i++)
	{
		neigh[u[i]].push_back({v[i],c[i]});
		neigh[v[i]].push_back({u[i],c[i]});
	}
	int mn=1e9;
	for (int s = 0; s < n; s++)
	{
		vector<bool> keys(n,false);
		vector<unordered_set<int>> to_visit(n);
		vector<int> visited(n);
		queue<int> q;
		q.push(s);
		while(!q.empty()){
			int x=q.front(); q.pop();
			if(visited[x]==2) continue;
			visited[x]=2;
			if(!keys[r[x]]){
				for (auto _u : to_visit[r[x]])
				{
					if(visited[_u]>=1) continue;
					visited[_u]=1;
					q.push(_u);
				}
			}
			keys[r[x]]=true;
			for (auto _u : neigh[x])
			{
				if(visited[_u.first]>=1) continue;
				if(keys[_u.second]){
					visited[_u.first]=1;
					q.push(_u.first);
				}else{
					to_visit[_u.second].insert(_u.first);
				}
			}
		}
		int sm=-1;
		for (int i = 0; i < n; i++) sm+=(int)(visited[i]==2);
		ans[s]=sm;
		mn=min(mn,sm);
	}
	for (int i = 0; i < n; i++)
	{
		if(ans[i]==mn) ans[i]=1;
		else ans[i]=0;
	}
	return ans;
}

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