# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1261370 | hoa208 | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<int, int>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
#define t_test int t;cin >> t;while(t--)
const int mod = 1e9 + 7;
const int INF = 1e18;
inline void adm(int &x){if(x>=mod)x%=mod;else if(x<0)x+=mod;}
//--------------------------------------------------------------------
int n, m, q;
const int N = 1e5 + 10;
vector<int> g[N], h[N];
vector<pa> ens[N];
const int BLOCK = 100;
int dx[N], c[N], dp[N];
void hbmt() {
cin >> n >> m >> q;
FOR(i, 1, m) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
h[v].push_back(u);
}
FOR(i, 1, n) {
vector<pa> vt;
for(auto v : h[i]) {
for(auto e : ens[v]) {
vt.push_back({e.fi + 1, e.se});
}
}
sort(vt.begin(), vt.end(), [&] (pa &x, pa &y) {
return x.fi > y.fi;
});
int cnt = 0;
for(auto e : vt) {
if(dx[e.se] == 1) continue;
dx[e.se] = 1;
cnt++;
ens[i].push_back(e);
if(cnt >= BLOCK + 2) {
break;
}
}
ens[i].push_back({0, i});
for(auto e : vt) {
dx[e.se] = 0;
}
}
FOR(i, 1, q) {
int t, y;
cin >> t >> y;
FOR(j, 1, y) {
cin >> c[j];
dx[c[j]] = 1;
}
if(y <= BLOCK) {
bool ok = false;
for(auto e : ens[t]) {
if(dx[e.se] == 0) {
cout << e.fi << '\n';
ok = true;
break;
}
}
if(!ok) cout << -1 << '\n';
}
else {
fill(dp + 1, dp + t + 1, -1);
FOR(i, 1, t) {
if(!dx[i]) {
dp[i] = max(0LL, dp[i]);
}
if(dp[i] == -1) continue;
for(auto v : g[i]) {
dp[v] = max(dp[i] + 1, dp[v]);
}
}
cout << dp[t] << '\n';
}
FOR(j, 1, y) {
dx[c[j]] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen("hbmt.inp", "r")) {
freopen("hbmt.inp", "r", stdin);
freopen("hbmt.out", "w", stdout);
}
// t_test
hbmt();
return 0;
}