| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1209900 | Younis_Dwai | Bitaro’s Party (JOI18_bitaro) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
//#define int long long
#define in insert
#define mid (l+r)/2
//register int cnt
using namespace std;
const int N=1e5+5;
const int sqr=101;
vector<int> adj[N];
int n,m,Q,busy[N],d[N],vis[N],largest[N],c[N];
vector<pair<int,int>> best[N];
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
cin>>n>>m>>Q;
for(int i=1;i<=m;i++){
int x,y;cin>>x>>y;
adj[y].pb(x);
}
memset(largest,-1,sizeof largest);
for(int i=1;i<=n;i++){
best[i].pb({0,i});
vector<int> reach;
for(auto u : adj[i]){
for(auto[dis , from] : best[u]){
if(largest[from]==-1){
reach.pb(from);
largest[from]=1+dis;
vis[from]=1;
}
else{
largest[from]=max(1+dis,largest[from]);
}
}
}
for(auto u : reach){
best[i].pb({largest[u],u});
largest[u]=-1;
}
sort(best[i].rbegin(),best[i].rend());
while(best[i].size()>sqr) best[i].pop_back();
}
busy[0]=1;
while(Q--){
int node,cnt;cin>>node>>cnt;
vector<int> v;
for(int i=1;i<=cnt;i++){
cin>>c[i];
busy[c[i]]=1;
}
if(cnt<sqr){
int ret=-1;
for(auto u : best[node]){
if(busy[u.S]==0){
ret=u.F;
break ;
}
}
cout<<ret<<endl;
}
else{
for(int i=1;i<=node;i++) d[i]=-1;
d[node]=0;
for(int i=node;i>=1;i--){
if(dp[i]==-1) continue ;
for(auto u : adj[i]){
if(d[u]<1+d[node]){
d[u]=1+d[node];
}
}
}
int ret=-1;
for(int i=1;i<=node;i++){
if(busy[i] || d[i]==-1) continue ;
ret=max(ret,d[i]);
}
cout<<ret<<endl;
}
for(int i=1;i<=cnt;i++) busy[c[i]]=0;
}
return 0;
}