Submission #1368994

#TimeUsernameProblemLanguageResultExecution timeMemory
1368994ASGA_RedSeaBitaro’s Party (JOI18_bitaro)C++20
14 / 100
167 ms111332 KiB
/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/



/// author : "ASGA"


#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>


using namespace std;
using ll=long long;
using lll=__int128;




const int S=105;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);


    int n,m,q;cin>>n>>m>>q;
    vector<vector<int>>a(n);
    while(m--){
        int u,v;cin>>u>>v;
        u--;v--;
        a[v].push_back(u);
    }

    vector<vector<pair<int,int>>>d(n);
    vector<int>mx(n,0);
    
    vector<int>f(n,0);
    for(int i=0;i<n;i++){        
        vector<pair<int,int>>b={{0,i}};
        for(int&j:a[i]){
            for(auto&[v,k]:d[j])b.push_back({v+1,k});
        }
        for(auto&[v,k]:b){
            if(d[i].size()<=S&&f[k]==0)d[i].push_back({v,k});
            f[k]=max(f[k],v+1);
        }
        for(auto&[v,k]:d[i]){
            v=f[k]-1;
            f[k]=0;
        }
    }
    for(int i=0;i<n;i++)d[i].push_back({-1,-1});

    f.assign(n,0);
    while(q--){
        int u,k;cin>>u>>k;u--;
        vector<int>b(k);
        for(int&v:b){cin>>v;v--;}
        if(k>S){
            vector<int>ff(n,0);
            int jj=0;
            for(int i=0;i<=u;i++){
                if(jj<k&&b[jj]==i){ff[i]=1;jj++;}
                for(int&j:a[i]){
                    ff[i]&=ff[j];
                }
            }

            for(int i=0;i<=u;i++){
                mx[i]=0;
                for(int&j:a[i]){
                    if(!ff[j])mx[i]=max(mx[i],mx[j]+1);
                }
            }
            cout<<(ff[u]?-1:mx[u])<<'\n';
        }
        else{
            for(int&i:b)f[i]=1;

            
            for(auto&[v,kk]:d[u]){
                if(!f[kk]){
                    cout<<v<<'\n';
                    break;
                }
            }

            for(int&i:b)f[i]=0;
        }
    }
    
    
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...