Logo Wy Online Judge

WyOJ

Paste!

#include <array>
#include <iostream>
#include <map>
#include <vector>

int main() {
	using namespace std;
	int n, m, k;
	cin >> n >> m >> k;
	auto rest = new vector<int>[n];
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		rest[i].resize(x);
		for (auto& j : rest[i])
		{
			cin >> j;
			--j;
		}
	}
	auto arr = new int[m];
	for (int i = 0; i < m; i++)
	{
		cin >> arr[i];
		--arr[i];
	}
	array<map<int, int>, 2> dp;
	dp[1][n] = 0;
	for (int i = 0, fl = 0; i < m; i++, fl ^= 1)
	{
		for (auto j : rest[arr[i]])
		{
			dp[fl][j] = dp[fl ^ 1][n];
			if (dp[fl ^ 1].contains(j))
				dp[fl][j] = min(dp[fl][j], dp[fl ^ 1][j]);
			dp[fl ^ 1].erase(j);
		}
		dp[fl][n] = dp[fl ^ 1][n] + 1;
		for (const auto& [j, val] : dp[fl ^ 1])
			dp[fl][n] = min(dp[fl][n], val + 1);
	}
	int ans = m + n;
	for (const auto& [i, val] : dp[m % 2 ^ 1])
		ans = min(ans, val);
	cout << ans << endl;
	delete[] arr;
	delete[] rest;
	return 0;
}