Submission #446422

#	Time	Username	Problem	Language	Result	Execution time	Memory
446422		luciocf	Keys (IOI21_keys)	C++17	9 / 100	102 ms	16280 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];

void bfs(int s)
{
	deque<pii> dq;
	set<int> st;
	map<pii, int> mark;

	dq.push_front({s, a[s]});
	st.insert(a[s]);

	while (!dq.empty())
	{
		int u = dq.front().ff, k = dq.front().ss; dq.pop_front();

		if (st.find(k) == st.end()) continue;

		st.insert(a[u]);
		ans[s]++;

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

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

			if (st.find(w) == st.end()) dq.push_back({v, w});
			else dq.push_front({v, 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++)
		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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33