Submission #674527

#	Time	Username	Problem	Language	Result	Execution time	Memory
674527		Denkata	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2062 ms	251376 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 3000;
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[600][100006];
int durvo[600][400006];
int f[100006],mx[100006];
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 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 dfs(int u)
{
    int otg = -1;
    if(f[u]==br)
        return mx[u];
    f[u]=br;
    mx[u]=-1;
    if(queried[u]!=br)mx[u]=0;
    //cout<<u<<" ud "<<d<<endl;
    if(nom[u]!=0)
    {
        ///big
        ans=-1;
        int l=1;
        for(int ii=1; ii<=y; ii++)
        {
            int jj=vr[ii]-1;
            if(l<=jj)
                query(nom[u],l,jj);
            l=vr[ii]+1;
        }
        if(l<=n)
            query(nom[u],l,n);
        return mx[u]=ans;
    }
    else
    {
        for(auto j:obr[u])
        {
            int val=dfs(j);
            if(val==-1)
                continue;
            mx[u]=max(mx[u],val+1);
        }
    }
    //cout<<u<<" "<<mx[u]<<endl;
    return mx[u];
}
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);
        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);
            cout<<ans<<endl;
        }
        else
        {
            ///small
            cout<<dfs(t)<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:42:9: warning: unused variable 'otg' [-Wunused-variable]
   42 |     int otg = -1;
      |         ^~~

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