Submission #1049156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049156		amine_aroua	Keys (IOI21_keys)	C++17	0 / 100	3094 ms	348 KiB

keys

#include <bits/stdc++.h>
using namespace std;
int n ;
vector<vector<pair<int, int>>> adj;
vector<int> r;
vector<bool> vis;
bool comp(const pair<int, int> &a ,const pair<int ,int> &b)
{
	if(vis[b.first])
		return 1;
	return 0;
}
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<pair<int ,int>> pq;
		vis.assign(n , 0);
		vis[r[i]] = 1;
		pq.push_back({r[i] , i});
		while(!pq.empty())
		{
			sort(pq.begin() , pq.end() , comp);
			auto tp = pq.back();
			pq.pop_back();
			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_back({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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33