Submission #1318757

#TimeUsernameProblemLanguageResultExecution timeMemory
1318757exoworldgdBitaro’s Party (JOI18_bitaro)C++20
100 / 100
917 ms513120 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<pair<int,int>>best[N];
void combine(vector<pair<int,int>>&a,vector<pair<int,int>>&b){
    vector<pair<int,int>>ans;
    int j=0;
    for(int i=0;i<a.size();i++)if(ans.size()<B){
        while(j<b.size()&&b[j].first>a[i].first&&ans.size()<B){if(!used[b[j].second])used[b[j].second]=1,ans.push_back(b[j]);j++;}
        if(ans.size()==B)break;
        if(!used[a[i].second])ans.push_back(a[i]),used[a[i].second]=1;
    }
    while(j<b.size()&&ans.size()<B){if(!used[b[j].second])used[b[j].second]=1,ans.push_back(b[j]);j++;}
    a=ans;
    for(auto i:ans)used[i.second]=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])combine(best[i],best[v]);
        if(best[i].size()<B)best[i].push_back({-1,i});
        for(auto&j:best[i])j.first++;
    }
    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.second]){ans=i.first;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...