제출 #796659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796659		Johann	열쇠 (IOI21_keys)	C++17	9 / 100	3067 ms	28244 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);
	vis[node] = true;

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

	while (!q.empty())
	{
		int v = q.front(), u, k;
		q.pop();
		for (pii e : adj[v])
		{
			tie(u, k) = e;
			if (vis[u])
				continue;

			if (keys[k])
			{
				vis[u] = true;
				q.push(u);
				if (!keys[R[u]])
				{
					keys[R[u]] = true;
					while (!waiting[R[u]].empty())
					{
						if (!vis[waiting[R[u]].back()])
							q.push(waiting[R[u]].back());
						waiting[R[u]].pop_back();
					}
				}
			}
			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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33