Submission #446432

#	Time	Username	Problem	Language	Result	Execution time	Memory
446432		luciocf	Keys (IOI21_keys)	C++17	20 / 100	3066 ms	16472 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e3+10;

int a[maxn];
int ans[maxn];

vector<pii> grafo[maxn];

vector<int> edge[maxn];

bool mark[maxn];

void bfs(int s)
{
	memset(mark, 0, sizeof mark);

	set<int> st;
	set<pii> ord;
	map<pii, int> mp;

	st.insert(a[s]);
	edge[a[s]].push_back(s);
	ord.insert({1, a[s]});

	while (ord.size())
	{
		pii pp = *ord.begin();

		ord.erase(pp);
		if (pp.ff-1 > 0) ord.insert({pp.ff-1, pp.ss});

		int u = edge[pp.ss].back();
		edge[pp.ss].pop_back();

		if (st.find(a[u]) == st.end() && edge[a[u]].size() > 0)
			ord.insert({edge[a[u]].size(), a[u]});

		st.insert(a[u]);

		if (!mark[u]) ans[s]++;
		mark[u] = 1;

		for (auto pp: grafo[u])
		{
			int v = pp.ff, w = pp.ss;

			if (mp[{v, w}]) continue;
			mp[{v, w}] = 1;

			edge[w].push_back(v);

			if (ord.find({(int)edge[w].size()-1, w}) != ord.end())
				ord.erase({(int)edge[w].size()-1, w});

			if (st.find(w) != st.end()) ord.insert({edge[w].size(), w});
		}
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
	int n = r.size(), m = u.size();

	for (int i = 1; i <= n; i++)
		a[i] = r[i-1]+1;

	for (int i = 0; i < m; i++)
	{
		grafo[u[i]+1].push_back({v[i]+1, c[i]+1});
		grafo[v[i]+1].push_back({u[i]+1, c[i]+1});
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			edge[j].clear();

		bfs(i);
	}

	vector<int> final;

	int mn = *min_element(ans+1, ans+n+1);

	for (int i = 1; i <= n; i++)
	{
		if (ans[i] == mn) final.push_back(1);
		else final.push_back(0);
	}

	return final;
}

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