Submission #776394

#	Time	Username	Problem	Language	Result	Execution time	Memory
776394		aryan12	Keys (IOI21_keys)	C++17	37 / 100	177 ms	36320 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5 + 5;
vector<array<int, 2> > g[N];
vector<int> key_types;
int n, m;

vector<int32_t> solve1()
{
	vector<int32_t> ans;
	int current_count = 1e18;
	for(int i = 0; i < n; i++)
	{
		int total_count = 0;
		vector<int> colors[n + 1];
		vector<bool> already_found(n + 1, false), vis(n + 1, false);
		vis[i] = true;
		queue<int> q;
		q.push(i);
		while(!q.empty())
		{
			int node = q.front();
			total_count += 1;
			q.pop();
			already_found[key_types[node]] = true;
			for(int to: colors[key_types[node]])
			{
				if(vis[to]) continue;
				vis[to] = true;
				q.push(to);
			}
			colors[key_types[node]].clear();
			for(auto [to, req]: g[node])
			{
				if(vis[to]) continue;
				if(already_found[req])
				{
					vis[to] = true;
					q.push(to);
				}
				colors[req].push_back(to);
			}
		}
		if(total_count < current_count)
		{
			ans.clear();
			current_count = total_count;
		}
		if(total_count == current_count)
		{
			ans.push_back(i);
		}
	}
	return ans;
}

vector<int32_t> find_reachable(vector<int32_t> r, vector<int32_t> u, 
	vector<int32_t> v, vector<int32_t> c) 
{
	n = r.size(), m = c.size();
	vector<int32_t> ans(n, 0);
	for(int i = 0; i < n; i++)
	{
		key_types.push_back(r[i]);
	}
	for(int i = 0; i < m; i++)
	{
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
	if(n <= 2000 and m <= 2000)
	{
		vector<int32_t> cur_ans = solve1();
		for(int i: cur_ans)
		{
			ans[i] = 1;
		}
	}
	return ans;
}

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