Submission #1049152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049152		amine_aroua	Keys (IOI21_keys)	C++17	9 / 100	3044 ms	28564 KiB

keys

#include <bits/stdc++.h>
using namespace std;
int n ;
vector<vector<pair<int, int>>> adj;
vector<int> r;
vector<bool> vis;
class comp
{
	public:
	bool operator()(const pair<int, int> &a ,const pair<int ,int> &b)
	{
		return vis[a.first]< vis[b.first];
	}
};
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);
		priority_queue<pair<int ,int> , vector<pair<int ,int>> , comp> pq;
		vis.assign(n , 0);
		vis[r[i]] = 1;
		pq.push({r[i] , i});
		while(!pq.empty())
		{
			auto tp = pq.top();
			pq.pop();
			if(!vis[tp.first])
			{
				break;
			}
			int node = tp.second;
			if(reach[node])
			{
				continue;
			}
			reach[node] = 1;
			vis[r[node]] = 1;
			for(auto [u , key] : adj[node])
			{
				if(!reach[u])
				{
					pq.push({key , u});
				}
			}
		}
		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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33