Submission #1049323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049323		amine_aroua	Keys (IOI21_keys)	C++17	9 / 100	88 ms	37476 KiB

keys

#include <bits/stdc++.h>
using namespace std;
struct DSU
{
	vector<int> e;
	DSU(int n)
	{
		e.assign(n,  -1);
	}
	int get(int x)
	{
		return (e[x] < 0 ? x : e[x] = get(e[x]));
	}
	int sz(int x)
	{
		return -e[get(x)];
	}
	void unite(int u ,int v)
	{
		u = get(u) ,v = get(v);
		if(u == v)
			return;
		if(e[u] > e[v])
			swap(u , v);
		e[u]+=e[v];
		e[v] = u;
	}
};
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]});
	}
	bool empty = 0;
	for(int i = 0 ; i < n ;i++)
	{
		bool acc = 0;
		for(auto [j , key] : adj[i])
		{
			if(r[i] == key)
			{
				acc = 1;
				break;
			}
		}
		if(!acc)
		{
			empty = 1;
			break;
		}
	}
	vector<int> ret(n);
	if(empty)
	{
		for(int i = 0 ; i < n ;i++)
		{
			bool acc = 0;
			for(auto [j , key] : adj[i])
			{
				if(r[i] == key)
				{
					acc = 1;
					break;
				}
			}
			if(!acc)
				ret[i] = 1;
		}
		return ret;
	}
	DSU dsu(n);
	for(int i = 0 ; i < n ; i++)
	{
		for(auto [j , key] : adj[i])
		{
			if(r[i] == r[j] && r[i] == key)
			{
				dsu.unite(i , j);
			}
		}
	}
	int mn = 1e9;
	for(int i = 0 ; i < n; i++)
	{
		if(dsu.sz(i) != 1)
		{
			mn = min(mn , dsu.sz(i));
		}
	}
	for(int i = 0 ; i < n ; i++)
	{
		if(dsu.sz(i) == mn)
		{
			ret[i] = 1;
		}
	}
	return ret;
}

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