#ifdef ONPC
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#ifndef ONPC
#pragma GCC target("avx")
#pragma GCC target("popcnt")
#define cerr if (false) cerr
#endif
using namespace std;
#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
return uniform_int_distribution<ll>(l, r)(gen64);
}
template<class T>
bool umin(T &a, const T &b) {
return (a > b ? a = b, true : false);
}
template<class T>
bool umax(T &a, const T &b) {
return (a < b ? a = b, true : false);
}
const int mod = 998244353;
ll mult(ll a, ll b) {
return (a * b) % mod;
}
template<class T>
void add(T &a, const T &b) {
a = (a + b) % mod;
}
const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;
const int maxn = 2e5 + 10, maxc = 10;
constexpr int sqn = 50;
vector<int> g[maxn];
void solve() {
int n, m, q;
cin >> n >> m >> q;
for (int e = 0; e < m; ++e) {
int v, u;
cin >> v >> u; v--, u--;
g[v].push_back(u);
}
vector<set<Pint>> small(n);
vector<map<int, int>> mp(n);
auto insert = [&](int i, Pint x) {
auto &m = mp[i];
auto &s = small[i];
if (m.count(x.second)) {
if (m[x.second] > x.first) {
return;
}
s.erase({m[x.second], x.second});
}
s.insert(x);
m[x.second] = x.first;
if (s.size() > sqn) {
m.erase(s.begin()->second);
s.erase(s.begin());
}
};
for (int i = 0; i < n; ++i) {
// small[i].push_back({0, i});
insert(i, {0, i});
}
for (int v = 0; v < n; ++v) {
// sort(all(small[v]), greater<>());
// if (small[v].size() > sqn) {
// small[v].resize(sqn);
// }
for (int u : g[v]) {
for (auto [l, p] : small[v]) {
insert(u, {l + 1, p});
// small[u].push_back({l + 1, p});
}
}
}
vector<bool> used(n);
vector<int> dp(n);
auto calc_big = [&](int t) {
for (int i = 0; i < n; ++i) {
dp[i] = (used[i] ? -inf : 0);
}
for (int v = 0; v < n; ++v) {
for (int u : g[v]) {
umax(dp[u], dp[v] + 1);
}
}
return max(dp[t], -1);
};
while (q--) {
int t, y;
cin >> t >> y; t--;
vector<int> c(y);
for (auto &v : c) {
cin >> v; v--;
}
for (auto v : c) {
used[v] = true;
}
if (y < sqn) {
int ans = -1;
for (auto [l, v] : small[t]) {
if (!used[v]) {
umax(ans, l);
}
}
cout << ans << '\n';
} else {
cout << calc_big(t) << '\n';
}
for (auto v : c) {
used[v] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |