Submission #1151096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151096		adkjt	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1419 ms	218072 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;

vector<int> g[111111],a[111111];
int mx[111111],dis[111111];
vector<pair<int,int>> now[111111];
int closed[111111];
const int sq=150;
int main()
{
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        g[v].push_back(u);
        a[u].push_back(v);
    }
    memset(mx,-1,sizeof mx);
    for(int i=1;i<=n;i++)
    {
        now[i].push_back({0,i});
        vector<int> use;
        for(auto x:g[i])
        {
            for(auto xx: now[x])
            {
                if(mx[xx.second]==-1)
                {
                    mx[xx.second]=xx.first+1;
                    use.push_back(xx.second);
                }
                else mx[xx.second]=max(mx[xx.second],xx.first+1);
            }
        }
        for(auto x:use)
        {
            now[i].push_back({mx[x],x});
            mx[x]=-1;
        }
        sort(now[i].begin(),now[i].end());
        reverse(now[i].begin(),now[i].end());
        while(now[i].size()>sq) now[i].pop_back();

    }
    while(q--)
    {
        int T,Y;cin>>T>>Y;
        for(int i=1;i<=n;i++) closed[i]=0;
        for(int i=1;i<=Y;i++)
        {
            int x;cin>>x;
            closed[x]=1;
        }
        if(Y>sq)
        {
            int ans=-1;
            for(int i=1;i<=n;i++) dis[i]=INT_MIN;
            dis[T]=0;
            for(int i=T;i>0;i--)
            {
                for(auto x:a[i])
                {
                    dis[i]=max(dis[i],dis[x]+1);
                }
                if(closed[i]) continue;
                ans=max(ans,dis[i]);
            }

            cout<<ans<<'\n';
        }
        else
        {
            int ch=0;
            for(auto x:now[T])
            {
                if(!closed[x.second])
                {
                    cout<<x.first<<'\n';
                    ch=1;
                    break;
                }
            }
            if(!ch) cout<<-1<<'\n';

        }

    }
}

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