제출 #369624

#제출 시각아이디문제언어결과실행 시간메모리
3696248e7Bitaro’s Party (JOI18_bitaro)C++14
14 / 100
2083 ms7024 KiB
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int siz = 320;
vector<int> adj[maxn];
int dp[maxn];
bool part[maxn];
void getdp(int n) {
	for (int i = 1;i <= n;i++) dp[i] = 0;
	for (int i = 1;i <= n;i++) {
		for (int v:adj[i]) {
			dp[v] = max(dp[v], (dp[i] == 0 ? (part[i] ? -1 : 0) : dp[i]) + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}
	getdp(n);
	while (q--) {
		int ind, yi;
		cin >> ind >> yi;
		vector<int> val;
		for (int i = 0;i < yi;i++) {
			int x;
			cin >> x;
			part[x] = 1;
			val.push_back(x);
		}
		getdp(n);
		if (part[ind] && dp[ind] == 0) cout << -1 << "\n";
		else cout << dp[ind] << "\n";
		for (int i:val) part[i] = 0;
	}
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
 */

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...