This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 1000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int sq = 80 ;
int n , m , q , dp[maxn] ,z , mark[maxn] , cnt , c[maxn] , ans ;
vec<int> out[maxn] , in[maxn];
vec<pii> adj[maxn] , t ;
int main()
{
migmig ;
vec<int> T(maxn) ;
cin>>n>>m>>q ;
for(int i = 1 ; i <= m ; i ++ ){
int u , v ;
cin>>u>>v ;
if(u > v) swap(u , v) ;
out[u].pb(v) ;
in[v].pb(u) ;
}
/* for(int i = 1 ; i <= n ; i++ ){
for(auto u : in[i]){
dp[i] = max(dp[i] , dp[u] + 1) ;
}
// adj[i].pb({0 , i}) ;
}*/
for(int i = 1 ; i <= n ; i ++ ){
for(auto u : in[i]){
for(auto v : adj[u]){
t.pb({v.X + 1 , v.Y}) ;
}
/*z = sz(adj[i]) ;
for(auto u : adj[i]) cout<<u.X<<","<<u.Y << " " ; cout<<endl ; for(auto u : t) cout<<u.X <<"," << u.Y <<" " ; cout<<endl ;
merge(adj[i].begin() , adj[i].begin() + z , all(t) , T.begin() , greater<pii>()) ;
t.clear() ; */
}
t.pb({0 , i}) ;
cnt = 0 ;
sort(all(t) , greater<pii>()) ;
for(auto u : t){
if(!mark[u.Y]){
adj[i].pb({u.X , u.Y}) ; cnt++ ;
mark[u.Y] = 1 ;
}
if(cnt >= sq) break ;
}
t.clear() ;
for(auto u : adj[i]) mark[u.Y] = 0 ;
// adj[i].resize( min( (int)sz(adj[i]) , sq) ) ;
/*cout<<i <<" : " ;
for(auto u : adj[i]) cout<<u.X <<","<<u.Y <<" " ;
cout<<endl ; */
}
int v, k ;
while(q--){
cin>>v>>k ;
for(int i= 0 ; i < k ; i ++ ){
cin>>c[i] ;
mark[c[i]] = 1 ;
}
ans = -1 ;
if(k >= sq){
for(int i = 1 ; i <= n ; i ++ ) dp[i] = -mod ; dp[v] = 0 ;
/* for(int i = 1 ; i <= v ; i++ ){
if(!mark[i]) dp[i] = 0 ;
for(auto u : in[i]){
if(mark[u]) continue ;
dp[i] = max(dp[i] , dp[u] + 1) ;
}
}
if(dp[v] < 0 ) cout<<-1<<"\n" ; else cout<<dp[v] <<"\n" ; */
for(int i = v ; i >= 1 ; i -- ){
for(auto u : out[i]){
dp[i] = max(dp[i] , dp[u] + 1) ;
}
if(!mark[i]){
ans = max(ans , dp[i]) ;
}
}
cout<<ans<<"\n" ;
for(int i = 0 ; i < k ; i ++ ) mark[c[i]] = 0 ;
continue ;
}
for(auto u : adj[v]){
if(!mark[u.Y]){
ans = u.X ;
break ;
}
}
cout<<ans << "\n" ;
for(int i = 0 ; i < k ; i ++ ) mark[c[i]] = 0 ;
}
}
Compilation message (stderr)
bitaro.cpp: In function 'int main()':
bitaro.cpp:80:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
80 | for(int i = 1 ; i <= n ; i ++ ) dp[i] = -mod ; dp[v] = 0 ;
| ^~~
bitaro.cpp:80:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
80 | for(int i = 1 ; i <= n ; i ++ ) dp[i] = -mod ; dp[v] = 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... |