Submission #656069

#TimeUsernameProblemLanguageResultExecution timeMemory
656069FarbodBitaro’s Party (JOI18_bitaro)C++17
0 / 100
2 ms2644 KiB
/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Sun, 06 Nov 2022 (12:48:25)
*
*/
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 1;

int n, m, dp[N];
bool vis[N];
vector <int> adj[N];

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int q;
	cin >> n >> m >> q;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v, u--, v--;

		adj[v].push_back(u);
	}

	int r;
	while (q--) {
		int k, c;
		cin >> r >> k, r--;

		for (int i = 0; i < k; i++)
			cin >> c, vis[c - 1] = 1;
	}

	dp[r] = 0;
	for (int i = r - 1; i >= 0; i--) {
		dp[i] = -1;
		for (auto x: adj[i])
			if (x <= r)
				dp[i] = max(dp[i], dp[x] + 1);
	}

	int ans = -1;
	for (int i = 0; i <= r; i++)
		if (!vis[i])
			ans = max(ans, dp[i]);

	cout << ans;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...