Submission #674512

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

bitaro

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 447;
int i,j,p,q,n,m,k,Q,queried[100006],t,y,ans,nom[100006],cnt,vr[100006],br;
vector <int> v[100006],obr[100006];
vector <int> big;
int prec[450][100006];
int durvo[450][400006];
void calc(int u,int d)
{
    prec[nom[i]][u]=max(prec[nom[i]][u],d);
    for(auto j:obr[u])
        calc(j,d+1);
}
void dfs(int u,int d)
{
    //cout<<u<<" ud "<<d<<endl;
    if(prec[nom[u]][t]!=-1 && queried[u]!=br)
    {
        ans=max(ans,prec[nom[u]][t]+d);
        return ;
    }
    if(nom[u]!=0)
        return ;
    if(queried[u]!=br)
        ans=max(ans,d);
    for(auto j:obr[u])
    {
        dfs(j,d+1);
    }
}
void add_big(int u)
{
    nom[u]=++cnt;
}
void build(int id,int p=1,int l=1,int r=n)
{
    if(l==r)
    {
        durvo[id][p]=prec[id][l];
        return ;
    }
    build(id,p*2,l,(l+r)/2);
    build(id,p*2+1,(l+r)/2+1,r);
    durvo[id][p]=max(durvo[id][p*2],durvo[id][p*2+1]);
}
void query(int id,int ql,int qr,int p=1,int l=1,int r=n)
{
    if(r<ql || qr<l)
        return ;
    if(l>=ql && r<=qr)
    {
        ans=max(ans,durvo[id][p]);
        return ;
    }
    query(id,ql,qr,p*2,l,(l+r)/2);
    query(id,ql,qr,p*2+1,(l+r)/2+1,r);
}
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);
        obr[q].push_back(p);
    }
    for(i=1;i<=n;i++)
    {
        if(obr[i].size()>=crit)
        {
            add_big(i);
            big.push_back(i);
            calc(i,0);
        }
    }
    for(auto i:big)
    {
        build(nom[i]);
    }
    while(Q--)
    {
        cin>>t;
        cin>>y;
        br++;
        for(i=1;i<=y;i++)
        {
            cin>>vr[i];
            queried[vr[i]]=br;
        }
        ans=-1;
        if(nom[t]!=0)
        {
            ///big
            int l=1;
            for(i=1;i<=y;i++)
            {
                j=vr[i]-1;
                if(l<=j)
                    query(nom[t],l,j);
                l=vr[i]+1;
            }
            if(l<=n)
                query(nom[t],l,n);
        }
        else
        {
            ///small
            dfs(t,0);
        }
        cout<<ans<<endl;
    }
    return 0;
}

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