Submission #1159975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159975		denislav	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1232 ms	110712 KiB

bitaro

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

const int MAX=1e5+11;

int n,m,q,bl_sz=100;
vector<int> adj[MAX];

void read()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[v].push_back(u);
    }
}

int used[MAX];
vector<pair<int,int>> dp[MAX];

void precalc()
{
    for(int i=1;i<=n;i++)
    {
        vector<pair<int,int>> v;
        v.push_back({0,i});
        for(int nxt: adj[i])
        {
            for(pair<int,int> pa: dp[nxt]) v.push_back({pa.first+1,pa.second});
        }

        sort(v.begin(),v.end(),greater<pair<int,int>>());
        for(pair<int,int> pa: v)
        {
            if(used[pa.second]==i) continue;

            dp[i].push_back(pa);
            used[pa.second]=i;
            if((int)dp[i].size()==bl_sz) break;
        }

        //cout<<i<<":"<<"\n";
        //for(pair<int,int> pa: dp[i]) cout<<pa.first<<" "<<pa.second<<"\n";
    }
}

int banned[MAX];
bool ban[MAX];

void small(int u)
{
    int ans=-1;
    for(pair<int,int> pa: dp[u])
    {
        if(!ban[pa.second])
        {
            ans=pa.first;
            break;
        }
    }

    cout<<ans<<"\n";
}

int lg[MAX];

void big(int u)
{
    for(int i=1;i<=u;i++) lg[i]=-1;
    lg[u]=0;
    for(int i=u;i>1;i--)
    {
        if(lg[i]==-1) continue;
        for(int nxt: adj[i]) lg[nxt]=max(lg[nxt],lg[i]+1);
    }

    int ans=-1;
    for(int i=1;i<=u;i++)
    {
        if(!ban[i]) ans=max(ans,lg[i]);
    }

    cout<<ans<<"\n";
}

void queries()
{
    while(q--)
    {
        int t,k;
        cin>>t>>k;

        for(int i=1;i<=k;i++)
        {
            cin>>banned[i];
            ban[banned[i]]=1;
        }

        if(k<bl_sz) small(t);
        else big(t);

        for(int i=1;i<=k;i++)  ban[banned[i]]=0;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    read();
    precalc();
    queries();

    return 0;
}

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