#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll int
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll N=1e5+5,inf=1e18,B=300;
ll n,m,q,dp[N],Q[N];
vector<ll> adj_pos[N],adj_opp[N];
vector<pll> T[N],tmp,PV;
bitset<N> ban,vis;
void F(vector<pll> &T){
sort(T.begin(),T.end(),[](pll a,pll b){return a.ss>b.ss;});
if((ll)T.size()>B) T.resize(B);
}
void build(){
rep(i,1,n) T[i].push_back(mp(i,0));
rep(i,2,n){
for(ll j:adj_opp[i]){
PV.clear();
for(auto o:T[j]) PV.push_back(mp(o.ff,o.ss+1));
tmp.resize((ll)T[i].size()+(ll)PV.size());
merge(PV.begin(),PV.end(),T[i].begin(),T[i].end(),tmp.begin(),[](pll a,pll b){return a.ss>b.ss;});
T[i].clear();
for(ll k=0;k<(ll)tmp.size()&&(ll)T[i].size()<B;++k) if(!vis[tmp[k].ff]) vis[tmp[k].ff]=1,T[i].push_back(tmp[k]);
for(auto o:T[i]) vis[o.ff]=0;
}
}
}
ll SMALL(ll v){
for(auto o:T[v]) if(!ban[o.ff]) return o.ss;
return -1;
}
ll BIG(ll v){
fill(dp+1,dp+n+1,-1);
dp[v]=0;
for(ll i=v-1;i>=1;--i){
for(ll j:adj_pos[i]){
if(dp[j]==-1) continue;
dp[i]=max(dp[i],dp[j]+1);
}
}
ll ans=-1;
rep(i,1,v) if(!ban[i]) ans=max(ans,dp[i]);
return ans;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>q;
rep(i,1,m){
ll u,v;
cin>>u>>v;
if(u>v) swap(u,v);
adj_pos[u].push_back(v);
adj_opp[v].push_back(u);
}
build();
while(q--){
ll v,k,x;
cin>>v>>k;
rep(i,1,k) cin>>x,Q[i]=x,ban[x]=1;
if(k>=B) cout<<BIG(v)<<'\n';
else cout<<SMALL(v)<<'\n';
rep(i,1,k) ban[Q[i]]=0;
}
return 0;
}
Compilation message (stderr)
bitaro.cpp:10:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
10 | const ll N=1e5+5,inf=1e18,B=300;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |