Submission #674506

#	Time	Username	Problem	Language	Result	Execution time	Memory
674506		Denkata	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2081 ms	178808 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 448;
int i,j,p,q,n,m,k,Q,queried[100006],t,y,ans,nom[100006],cnt;
vector <int> v[100006];
vector <int> big;
vector <int> small;
int prec[450][100006];
void calc(int u,int d)
{
    prec[nom[i]][u]=max(prec[nom[i]][u],d);
    for(auto j:v[u])
        calc(j,d+1);
}
void dfs(int u,int d)
{
    //cout<<u<<" ud "<<d<<endl;
    if(prec[nom[u]][t]!=-1)
    {
        ans=max(ans,prec[nom[u]][t]+d);
        return ;
    }
    if(nom[u]!=0)
        return ;
    if(u==t)
    {
        ans=max(ans,d);
        return ;
    }
    for(auto j:v[u])
    {
        if(j<=t)dfs(j,d+1);
    }
}
void add_big(int u)
{
    nom[u]=++cnt;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>Q;
    memset(prec,-1,sizeof(prec));
    for(i=1;i<=m;i++)
    {
        cin>>p>>q;
        v[p].push_back(q);
    }
    for(i=1;i<=n;i++)
    {
        if(v[i].size()>=crit)
        {
            add_big(i);
            big.push_back(i);
            calc(i,0);
        }
        else small.push_back(i);
    }
    int br = 0;
    while(Q--)
    {
        cin>>t;
        cin>>y;
        br++;
        for(i=1;i<=y;i++)
        {
            cin>>p;
            queried[p] = br;
        }
        ans=-1;
        for(auto i:big)
        {
            if(queried[i]!=br)
                ans=max(ans,prec[i][t]);
        }
        for(auto i:small)
        {
            if(i>t)continue;
            if(queried[i]!=br)
            {
                dfs(i,0);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
///queries can be sorted

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