fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 2000005
  7. #define fi first
  8. #define se second
  9. #define i18 __int128_t
  10.  
  11.  
  12. using namespace std;
  13.  
  14. int n,m;
  15. ll f[75][205];
  16.  
  17. int main()
  18. {
  19.     itachi
  20.     cin>>n>>m;
  21.     for(int i=1;i<=m;i++){
  22.         int u,v;
  23.         cin>>u>>v;
  24.         f[u][0] |= (1LL<<(v-1));
  25.     }
  26.     for(int j=1;j<=60;j++){
  27.         for(int u=1;u<=n;u++){
  28.             ll cur=f[u][j-1];
  29.             ll mask=0;
  30.             while(cur){
  31.                 int v=__builtin_ctzll(cur);
  32.                 cur &=(cur-1);
  33.                 mask |= f[v+1][j-1];
  34.             }
  35.             f[u][j]=mask;
  36.         }
  37.     }
  38.  
  39.     int q;cin>>q;
  40.     while(q--){
  41.         int k; cin>>k;
  42.         vector<int> s(k);
  43.         for(int i=0;i<k;i++) cin>>s[i];
  44.         vector<ll> reach(k);
  45.         for(int i=0;i<k;i++) reach[i] = (1LL<<(s[i]-1));
  46.         ll meet = (1LL << n) - 1;
  47.         for(int i = 0; i < k; i++) meet &= reach[i];
  48.         if(meet) { cout << 0 << '\n'; continue; }
  49.         ll Time=0;
  50.         vector<ll> cur=reach;
  51.         for(int b=60;b>=0;b--){
  52.             vector<ll> nxt(k,0);
  53.             for(int i=0;i<k;i++){
  54.                 ll curr=cur[i];
  55.                 ll newmask=0;
  56.                 while(curr){
  57.                     int u=__builtin_ctzll(curr);
  58.                     curr &=(curr-1);
  59.                     newmask |= f[u+1][b];
  60.                 }
  61.                 nxt[i]=newmask;
  62.             }
  63.             ll meet=-1;
  64.             for(int i=0;i<k;i++) meet &= nxt[i];
  65.             if(meet==0){
  66.                Time+=(1LL<<b);
  67.                cur.swap(nxt);
  68.             }
  69.         }
  70.         vector<ll> nxt(k);
  71.         for(int i = 0; i < k; i++) {
  72.             ll mask = cur[i], newmask = 0;
  73.             while(mask) {
  74.                 int u = __builtin_ctzll(mask);
  75.                 mask &= (mask-1);
  76.                 newmask |= f[u+1][0];
  77.             }
  78.             nxt[i] = newmask;
  79.         }
  80.  
  81.         meet = (1LL << n) - 1;
  82.         for(int i = 0; i < k; i++) meet &= nxt[i];
  83.  
  84.         if(meet) cout << Time + 1 << '\n';
  85.         else cout << -1 << '\n';
  86.     }
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FlKWHl
language:
C++14 (clang 8.0)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!