Submission #1250474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250474		I_FloPPed21	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	562 ms	270632 KiB

bitaro

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=1e5+5,B=100;
struct drum
{
    int nod;
    long long cost;
    bool operator<(const drum &other)
    {
        return cost>other.cost;
    }

};
vector<int>adj[N+1];
vector<drum>drumuri[N+1];
int n,m,q;
void read()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[b].push_back(a);
    }
}
void precalc()
{
    vector<long long>best(n+1,-1);
    for(int i=1;i<=n;i++)
    {
        vector<int>where;
        drumuri[i].push_back({i,0});
        for(auto u:adj[i])
        {
            for(auto [nod,dist]:drumuri[u])
            {
                if(best[nod]==-1)
                {
                    where.push_back(nod);
                    best[nod]=dist+1;
                }
                else
                {
                    best[nod]=max(best[nod],dist+1);
                }
            }
        }
        for(auto u:where)
        {
            drumuri[i].push_back({u,best[u]});
            best[u]=-1;
        }
        sort(drumuri[i].begin(),drumuri[i].end());
        while(drumuri[i].size()>B)
            drumuri[i].pop_back();
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    precalc();
    vector<int>used(n+1,0);
    vector<long long>best2(n+1,-1);
    for(int i=1;i<=q;i++)
    {
        int unde,cate;
        cin>>unde>>cate;
        vector<int>idx(cate+1);
        for(int j=1;j<=cate;j++)
        {
            cin>>idx[j];
            used[idx[j]]=true;
        }
        long long ans=-1;
        if(cate>=B)
        {
            best2[unde]=0;
            for(int k=unde;k>=1;k--)
            {
                if(!used[k])
                    ans=max(ans,best2[k]);
                if(best2[k]==-1)
                    continue;
                for(auto u:adj[k])
                {
                    best2[u]=max(best2[u],best2[k]+1);
                }
                best2[k]=-1;
            }

        }
        else
        {
            for(auto [u,dist]:drumuri[unde])
            {
                if(!used[u])
                    ans=max(ans,dist);
            }
        }
        for(int j=1;j<=cate;j++)
            used[idx[j]]=false;
        cout<<ans<<'\n';
    }
    return 0;
}

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