제출 #1340920

#제출 시각아이디문제언어결과실행 시간메모리
1340920jenterjongle45Bitaro’s Party (JOI18_bitaro)C++20
0 / 100
1 ms580 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,q;cin>>n>>m>>q;
    vector<vector<int>> rev(n+1);
    vector<vector<pii>> mst(n+1);
    vector<int> dp(n+1,0);
    while(m--){
        int u,v;cin>>u>>v;
        rev[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        for(int x:rev[i]){
            dp[i]=max(dp[i],dp[x]+1);
            mst[i].push_back({1,x});
            for(auto w:mst[x]) mst[i].push_back({w.first+1,w.second});
        }
        sort(mst[i].begin(),mst[i].end(),greater<pii>());
        while(mst[i].size()>=330) mst.pop_back();
    }
    vector<int> ch(n+1);
    while(q--){
        int t,N;cin>>t>>N;
        vector<int> tmp;
        for(int i=0;i<N;i++){
            int x;cin>>x;
            tmp.push_back(x);
            ch[x]=1;
        }
        for(auto x:mst[t]){
            if(!ch[x.second]){
                // cout<<x.second<<" ";
                cout<<x.first<<'\n';
                goto nx;
            }
        }
        for(int i=1;i<=t;i++){
            dp[i]=0;
            if(ch[i]){
                dp[i]=-1;
                continue;
            }
            for(int x:rev[i]){
                if(dp[x]==-1) continue;
                dp[i]=max(dp[i],dp[x]+1);
            }
        }
        cout<<dp[t]<<'\n';
        nx:;
        for(int x:tmp) ch[x]=0;
        tmp.clear();
        
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...