#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,q;
vector <int> z[1000005];
vector<pair<int,int>> lps[1000005];
int val[1000005];
int time1[100005];
int block;
bool cmp(pair<int,int> a,pair<int,int> b){
return a.second>b.second;
}
int del[1000005];
bool vis[1000005];
int max1=-1;
void dfs(int i,int dem){
if (del[i]!=q){
max1=max(max1,dem);
}
vis[i]=true;
for (auto p:z[i]){
if (vis[p]){
continue;
}
dfs(p,dem+1);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> q;
block=101;
for (int i=1;i<=b;i++){
int x,y;
cin >> x >> y;
z[y].push_back(x);
}
for (int i=1;i<=a;i++){
del[i]=1e16;
vector <int> v;
val[i]=0;
time1[i]=i;
v.push_back(i);
for (auto p:z[i]){
for (auto p1:lps[p]){
if (time1[p1.first]!=i){
time1[p1.first]=i;
val[p1.first]=p1.second+1;
v.push_back(p1.first);
}else{
val[p1.first]=max(val[p1.first],p1.second+1);
}
}
}
for (auto p:v){
lps[i].push_back({p,val[p]});
}
sort(lps[i].begin(),lps[i].end(),cmp);
int k=lps[i].size();
while (k>block){
lps[i].pop_back();
k--;
}
}
// for (int i=1;i<=a;i++){
// cout << lps[i][0].second << " ";
// }
// cout << "\n";
while (q--){
int t,x;
cin >> t >> x;
for (int i=1;i<=x;i++){
int y;
cin >> y;
del[y]=q;
}
if (x>block){
for (int i=1;i<=a;i++){
vis[i]=false;
}
max1=-1;
dfs(t,0);
cout << max1 << "\n";
}else{
int ans=-1;
for (auto p:lps[t]){
if (del[p.first]!=q){
ans=p.second;
break;
}
}
cout << ans << "\n";
}
}
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... |