Submission #884804

#	Time	Username	Problem	Language	Result	Execution time	Memory
884804		maxFedorchuk	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1646 ms	216908 KiB

bitaro

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

const long long MX=1e5+10;
const long long INF=1e18;

vector < pair < long long , long long > > shl[MX];

vector < long long > mas[MX];
vector < long long > lst(MX);
vector < long long > cnt(MX);

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

    long long n,m,q;
    cin>>n>>m>>q;

    long long a,b;
    for(long long i=0;i<m;i++)
    {
        cin>>a>>b;
        mas[b].push_back(a);
    }

    for(long long i=1;i<=n;i++)
    {
        vector < pair < long long , long long > > alcnt;

        for(auto u:mas[i])
        {
            for(auto y:shl[u])
            {
                alcnt.push_back({y.first+1,y.second});
            }
        }

        alcnt.push_back({0,i});

        sort(alcnt.begin(),alcnt.end());
        reverse(alcnt.begin(),alcnt.end());

        for(auto u:alcnt)
        {
            if(shl[i].size()>=100)
            {
                break;
            }

            if(lst[u.second]!=i)
            {
                lst[u.second]=i;
                shl[i].push_back(u);
            }
        }
    }


    for(long long i=1;i<=n;i++)
    {
        lst[i]=0;
    }

    for(long long nm=1;nm<=q;nm++)
    {
        long long plc,zb;
        cin>>plc>>zb;

        for(long long i=0;i<zb;i++)
        {
            cin>>a;
            lst[a]=nm;
        }

        if(zb<100)
        {
            bool o=0;

            for(auto u:shl[plc])
            {
                if(lst[u.second]!=nm)
                {
                    cout<<u.first<<"\n";
                    o=1;
                    break;
                }
            }

            if(!o)
            {
                cout<<"-1\n";
            }
        }
        else
        {
            for(long long i=1;i<=plc;i++)
            {
                cnt[i]=0;

                for(auto u:mas[i])
                {
                    cnt[i]=max(cnt[i],cnt[u]+1);
                }

                if(lst[i]==nm && cnt[i]==0)
                {
                    cnt[i]=-INF;
                }
            }

            if(cnt[plc]>=0)
            {
                cout<<cnt[plc]<<"\n";
            }
            else
            {
                cout<<"-1\n";
            }
        }
    }

    return 0;
}

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