#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, M = 111;
int n, m, Q, d[N], mark[N];
vector<int> adj[N];
vector<pair<int, int>> len[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> Q;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
vector<int> t;
t.push_back(i);
for (int v : adj[i])
for (auto [x, y] : len[v]) {
if (mark[y] != i) {
mark[y] = i;
d[y] = x + 1;
t.push_back(y);
} else d[y] = max(d[y], x + 1);
}
for (int v : t) len[i].push_back({ d[v], v });
sort(len[i].begin(), len[i].end(), greater<pair<int, int>>());
while (len[i].size() > M) len[i].pop_back();
}
memset(mark, 0, 4 * N);
for (int i = 1, s, y; i <= Q; i++) {
cin >> s >> y;
for (int j = 1, u; j <= y; j++) {
cin >> u;
mark[u] = i;
}
if (y >= M) {
memset(d, -1, 4 * N);
for (int u = 1; u <= n; u++) {
if (!mark[u]) d[u] = 0;
for (int v : adj[u])
if (d[v] != -1) d[u] = max(d[u], d[v] + 1);
}
cout << d[s] << '\n';
} else {
bool ok = 0;
for (auto [x, y] : len[s]) {
if (mark[y] == i) continue;
cout << x << '\n';
ok = 1;
break;
}
if (!ok) cout << -1 << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |