Submission #796689

#	Time	Username	Problem	Language	Result	Execution time	Memory
796689		Johann	Keys (IOI21_keys)	C++17	37 / 100	3066 ms	23864 KiB

keys

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<bool> vb;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M;
vvpii adj;
vi R;
vi P;

int find(int node)
{
	vb keys(N, 0);
	keys[R[node]] = 1;

	vb vis(N, false);

	vvi waiting(N);
	queue<int> q;
	q.push(node);

	while (!q.empty())
	{
		int v = q.front(), u, k;
		q.pop();

		if (vis[v])
			continue;
		vis[v] = true;

		if (!keys[R[v]])
			for (int x : waiting[R[v]])
				q.push(x);
		keys[R[v]] = true;

		for (pii e : adj[v])
		{
			tie(u, k) = e;

			if (vis[u])
				continue;

			if (keys[k])
				q.push(u);
			else
				waiting[k].push_back(u);
		}
	}

	return accumulate(all(vis), 1);
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
	N = sz(r), M = sz(u);
	R = r;
	adj.resize(N);
	for (int i = 0; i < sz(u); ++i)
		adj[u[i]].push_back({v[i], c[i]}),
			adj[v[i]].push_back({u[i], c[i]});

	P.resize(N);
	for (int i = 0; i < N; ++i)
		P[i] = find(i);
	int mini = *min_element(all(P));

	vi ans(N, 0);
	for (int i = 0; i < N; ++i)
		ans[i] = P[i] == mini;

	return ans;
}

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