Submission #928349

#	Time	Username	Problem	Language	Result	Execution time	Memory
928349		Aiperiii	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1323 ms	414104 KiB

bitaro

#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int N=1e5+5,sq=350;
vector <pair <int,int> > cct[N];
vector <int> g[N];
signed main(){
    
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[v].pb(u);
    }
    vector <int> d(n+1),ld(n+1),can;
    for(int i=1;i<=n;i++){
        d[i]=0;
        can.pb(i);
        for(auto edg : g[i]){
            for(auto x : cct[edg]){
                if(ld[x.ss]==i){
                    d[x.ss]=max(d[x.ss],x.ff+1);
                }
                else{
                    d[x.ss]=x.ff+1;
                    ld[x.ss]=i;
                    can.pb(x.ss);
                }
            }
        }
        sort(all(can),[&](int a, int b){return d[a]>d[b];});
        for(int j=0;j<min((int)can.size(),sq);j++){
            int x=can[j];
            cct[i].pb({d[x],x});
        }
        /*cout<<i<<"\n";
        for(auto x :cct[i])cout<<x.ff<<" "<<x.ss<<"\n";
        cout<<"\n";*/
        can.clear();
    }
    
    vector <int> no(n+1),dp(n+1);
    while(q--){
        int t,s;
        cin>>t>>s;
        vector <int> a(s);
        for(int i=0;i<s;i++){
            cin>>a[i];
            no[a[i]]=1;
            dp[a[i]]=-1e9;
        }
        int ans=-1;
        if(s<sq){
            for(auto x : cct[t]){
                if(!no[x.ss]){
                    ans=x.ff;
                    break;
                }
            }
        }
        else{
            for(int i=1;i<=t;i++){
                for(auto edg : g[i]){
                    dp[i]=max(dp[i],dp[edg]+1);
                }
                
            }
            ans=max(ans,dp[t]);
            for(int i=1;i<=t;i++){
                dp[i]=0;
            }
            
        }
        cout<<ans<<"\n";
        for(int i=0;i<s;i++){
            no[a[i]]=0;
            dp[a[i]]=0;
        }
    }
}
/*

 */

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86