Submission #1125778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125778		Newtonabc	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1585 ms	410832 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=320;
vector<int> adj[N];
int dist[N],lupd[N],ph[N],dp[N],un[N];
vector<pair<int,int>> lp[N];
int main(){
    int n,m,q;
    cin>>n >>m >>q;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u >>v;
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        for(int v:adj[i]){
            for(pair<int,int> j:lp[v]){
                int val=j.first,u=j.second;
                if(lupd[u]!=i) lupd[u]=i,dist[u]=val+1;
                else dist[u]=max(dist[u],val+1);
            }
        }
        lp[i].push_back({0,i});
        for(int v:adj[i]){
            for(pair<int,int> j:lp[v]){
                int u=j.second;
                if(ph[u]==i) continue;
                ph[u]=i;
                lp[i].push_back({dist[u],u});
            }
        }
        sort(lp[i].begin(),lp[i].end(),greater<pair<int,int>>());
        while(lp[i].size()>=330) lp[i].pop_back();
    }
    while(q){
        int ed,amt,fd=-1;
        cin>>ed >>amt;
        for(int i=0;i<amt;i++){
            int inp;
            cin>>inp;
            un[inp]=q;
        }
        if(amt>=M){
            for(int i=1;i<=n;i++) dp[i]=0;
            for(int i=1;i<=ed;i++) for(int v:adj[i]) if(dp[v]!=0 || un[v]!=q) dp[i]=max(dp[i],dp[v]+1);
            if(dp[ed]==0 && un[ed]==q) cout<<-1 <<"\n";
            else cout<<dp[ed] <<"\n";
        }
        else{
            for(int i=0;i<lp[ed].size();i++){
                if(un[lp[ed][i].second]==q) continue;
                fd=lp[ed][i].first;
                break;
            }
            cout<<fd <<"\n";
        }
        q--; 

    }
}

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