제출 #1368987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368987		ASGA_RedSea	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1105 ms	111432 KiB

bitaro

/**

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

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

*/



/// 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});
        }
        sort(b.rbegin(),b.rend());
        for(auto&[v,k]:b){
            if(f[k]==0){
                d[i].push_back({v,k});
                if(d[i].size()>S)break;
            }
            f[k]=1;
        }
        for(auto&[v,k]:b)f[k]=0;
    }
    for(int i=0;i<n;i++)d[i].push_back({-1,-1});

    while(q--){
        int u,k;cin>>u>>k;u--;
        vector<int>b(k);
        for(int&v:b){cin>>v;v--;}
        if(k>S){
            sort(b.rbegin(),b.rend());
            vector<int>ff(n,0);
            for(int i=0;i<=u;i++){
                if(!b.empty()&&b.back()==i){
                    ff[i]=1;
                    b.pop_back();
                }
                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{
            set<int>s(b.begin(),b.end());

            
            for(auto&[v,kk]:d[u]){
                if(s.find(kk)==s.end()){
                    cout<<v<<'\n';
                    break;
                }
            }
        }
    }
    
    
    return 0;
}

• 서브태스크 1: 7 / 7
• 서브태스크 2: 7 / 7
• 서브태스크 3: 86 / 86