Submission #1103471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103471		hoangnoobpro	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2061 ms	6736 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define nmax 100007
#define fi first
#define se second
#define ll int
ll t=1,n,m=0,i=0,j=0,d=0,x=0,k=0,y=0,z,a[nmax],b[nmax],h[nmax],f[nmax],deg[nmax];
vector<ll>v[nmax],nah;
vector<pair<ll,ll>>luu[nmax],tam;
queue<ll>dq;
bool cmp(pair<ll,ll>a,pair<ll,ll>b)
{
    return a.fi>b.fi;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>t;
    for(i=1;i<=m;++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        deg[y]++;
    }
    for(i=1;i<=n;++i)if(!deg[i])dq.push(i);
    z=sqrt(n);
    while(dq.size()>0)
    {
        x=dq.front();
        dq.pop();
        luu[x].push_back({0,x});
        for(i=0;i<v[x].size();++i)
        {
            y=v[x][i];
//            if(luu[x].size())for(j=0;j<luu[x].size();++j)luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
            ///
            tam=luu[y];
            luu[y].clear();
            d=0;
            j=k=0;
            while(d<z)
            {
                if(j==luu[x].size()||k==tam.size())break;
                d++;
                if(luu[x][j].fi>=tam[k].fi)
                {
                    if(f[luu[x][j].se])continue;
                    luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
                    nah.push_back(luu[x][j].se);
                    f[luu[x][j].se]=1;
                    j++;
                    continue;
                }
                if(f[tam[k].se])continue;
                f[tam[k].se]=1;
                nah.push_back(tam[k].se);
                luu[y].push_back({tam[k].fi,tam[k].se});
                k++;
            }
            while(d<z&&j<luu[x].size())
            {
                if(f[luu[x][j].se])continue;
                f[luu[x][j].se]=1;
                nah.push_back(luu[x][j].se);
                luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
                j++;
            }
            while(d<z&&k<tam.size())
            {
                if(f[tam[k].se])continue;
                f[tam[k].se]=1;
                nah.push_back(tam[k].se);
                luu[y].push_back({tam[k].fi,tam[k].se});
                k++;
            }
            tam.clear();
            ///
            if(nah.size())
                for(j=0;j<nah.size();++j)
            {
                f[nah[j]]=0;
            }
            nah.clear();
            deg[y]--;
            if(deg[y]==0)dq.push(y);
        }
    }
    x=sqrt(n);
    while(t--)
    {
        cin>>y>>z;
        for(i=1;i<=z;++i)
        {
            cin>>b[i];
            f[b[i]]=1;
        }
        ///
        if(z<x)
        {
           d=-1;
           for(i=0;i<luu[y].size();++i)
           {
               if(!f[luu[y][i].se])d=max(d,luu[y][i].fi);
           }
           if(!f[y]&&d<0)d=0;
           cout<<d<<"\n";
           for(i=1;i<=z;++i)f[b[i]]=0;
           continue;
        }
        ///
        d=-1;
        for(i=1;i<=y;++i)
            if(!f[i]||h[i])
        {
            for(j=0;j<v[i].size();++j)
            {
                h[v[i][j]]=max(h[v[i][j]],h[i]+1);
            }
        }
        if(h[y])d=h[y];
        if(!f[y]&&d<0)d=0;
        cout<<d<<"\n";
        for(i=1;i<=n;++i)f[i]=h[i]=0;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(i=0;i<v[x].size();++i)
      |                 ~^~~~~~~~~~~~
bitaro.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 if(j==luu[x].size()||k==tam.size())break;
      |                    ~^~~~~~~~~~~~~~~
bitaro.cpp:44:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                 if(j==luu[x].size()||k==tam.size())break;
      |                                      ~^~~~~~~~~~~~
bitaro.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             while(d<z&&j<luu[x].size())
      |                        ~^~~~~~~~~~~~~~
bitaro.cpp:69:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             while(d<z&&k<tam.size())
      |                        ~^~~~~~~~~~~
bitaro.cpp:80:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 for(j=0;j<nah.size();++j)
      |                         ~^~~~~~~~~~~
bitaro.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |            for(i=0;i<luu[y].size();++i)
      |                    ~^~~~~~~~~~~~~~
bitaro.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for(j=0;j<v[i].size();++j)
      |                     ~^~~~~~~~~~~~

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