Submission #1049221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049221		amine_aroua	Keys (IOI21_keys)	C++17	37 / 100	3062 ms	70936 KiB

keys

#include <bits/stdc++.h>
using namespace std;
int n ;
vector<vector<pair<int, int>>> adj;
vector<int> r;
std::vector<int> find_reachable(std::vector<int> r_, std::vector<int> u, std::vector<int> v, std::vector<int> c) 
{
	n = (int)r_.size();
	r = r_;
	adj.assign(n , {});
	for(int i = 0 ; i < (int)u.size() ; i++)
	{
		adj[u[i]].push_back({v[i] , c[i]});
		adj[v[i]].push_back({u[i] , c[i]});
	}
	
	vector<bool> reach(n);
	vector<int> p(n);
	int mn = 1e9;
	for(int i = 0 ; i < n ;i++)
	{
		reach = vector<bool>(n);
		vector<int> wait[n];
		wait[r[i]].push_back(i);
		int x = r[i];
		vector<int> available;
		available.push_back(r[i]);
		while(!available.empty())
		{
			x = available.back();
			if(wait[x].empty())
			{
				available.pop_back();
				continue;
			}
			int node = wait[x].back();
			wait[x].pop_back();
			reach[node] = 1;
			for(auto [u , key] : adj[node])
			{
				if(!reach[u])
				{
					wait[key].push_back(u);
				}
			}
			available.push_back(r[node]);
		}
		for(int j = 0 ; j < n ; j++)
		{
			p[i]+=reach[j];
		}
		mn = min(mn , p[i]);
	}
	vector<int> ret(n);
	for(int i = 0 ; i < n ;i++)
	{	
		ret[i] = (p[i] == mn);
	}
	return ret;
}

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