Submission #1318758

#TimeUsernameProblemLanguageResultExecution timeMemory
1318758exoworldgdBitaro’s Party (JOI18_bitaro)C++20
100 / 100
936 ms513188 KiB
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define int long long
using namespace std;
const int inf=LLONG_MAX,mod=1e9+7,N=1e5+5,B=320;
int n,m,q,dp[N],used[N];
vector<int>g[N];
vector<array<int,2>>best[N];
void merge(vector<array<int,2>>&a,vector<array<int,2>>&b){
    vector<array<int,2>>ans;
    int j=0;
    for(int i=0;i<a.size();i++)if(ans.size()<B){
        while(j<b.size()&&b[j][0]>a[i][0]&&ans.size()<B){if(!used[b[j][1]])used[b[j][1]]=1,ans.push_back(b[j]);j++;}
        if(ans.size()==B)break;
        if(!used[a[i][1]])ans.push_back(a[i]),used[a[i][1]]=1;
    }
    while(j<b.size()&&ans.size()<B){if(!used[b[j][1]])used[b[j][1]]=1,ans.push_back(b[j]);j++;}
    a=ans;
    for(auto i:ans)used[i[1]]=0;
}
signed main(void) {
    exoworldgd;
    cin>>n>>m>>q;
    for(int i=0,u,v;i<m;i++)cin>>u>>v,g[v].push_back(u);
    for(int i=1;i<=n;i++){
        for(int v:g[i])merge(best[i],best[v]);
        if(best[i].size()<B)best[i].push_back({-1,i});
        for(auto&j:best[i])j[0]++;
    }
    for(int t,y,ans;q--;){
        cin>>t>>y;
        if(y>=B){
            memset(dp,0,sizeof dp);
            for(int i=0,x;i<y;i++)cin>>x,dp[x]=-1e9;
            for(int i=1;i<=t;i++)for(int v:g[i])dp[i]=max(dp[i],dp[v]+1);
            cout<<max(dp[t],-1LL)<<"\n";
        }else{
            vector<int>a(y);
            for(int i=0;i<y;i++)cin>>a[i],used[a[i]]=1;
            ans=-1;
            for(auto i:best[t])if(!used[i[1]]){ans=i[0];break;}
            for(int i:a)used[i]=0;
            cout<<ans<<"\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...