Submission #1103492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103492		hoangnoobpro	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1367 ms	413460 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],cnt=0;
vector<ll>v[nmax];
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)
        {
            cnt++;
            y=v[x][i];
//            for(j=0;j<luu[x].size();++j)
//            {
//                luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
//            }
//            sort(luu[y].begin(),luu[y].end(),cmp);
//            continue;
            ///
            tam=luu[y];
            luu[y].clear();
            d=0;
            j=k=0;
            while(d<z)
            {
                if(j>=luu[x].size()&&k>=tam.size())break;
                if((j<luu[x].size()&&k<tam.size()&&luu[x][j].fi>=tam[k].fi)||k>=tam.size())
                {
                    if(f[luu[x][j].se]!=cnt)
                    {d++;
                    luu[y].push_back({luu[x][j].fi+1,luu[x][j].se});
                    f[luu[x][j].se]=cnt;}
                    j++;
                    continue;
                }
                if(k<tam.size()&&f[tam[k].se]!=cnt)
                {
                d++;
                f[tam[k].se]=cnt;
                luu[y].push_back({tam[k].fi,tam[k].se});}
                k++;
            }
            tam.clear();
            ///
            deg[y]--;
            if(deg[y]==0)dq.push(y);
        }
    }
    for(i=1;i<=n;++i)f[i]=0;
    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:50: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]
   50 |                 if(j>=luu[x].size()&&k>=tam.size())break;
      |                    ~^~~~~~~~~~~~~~~
bitaro.cpp:50: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]
   50 |                 if(j>=luu[x].size()&&k>=tam.size())break;
      |                                      ~^~~~~~~~~~~~
bitaro.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 if((j<luu[x].size()&&k<tam.size()&&luu[x][j].fi>=tam[k].fi)||k>=tam.size())
      |                     ~^~~~~~~~~~~~~~
bitaro.cpp:51: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]
   51 |                 if((j<luu[x].size()&&k<tam.size()&&luu[x][j].fi>=tam[k].fi)||k>=tam.size())
      |                                      ~^~~~~~~~~~~
bitaro.cpp:51:79: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 if((j<luu[x].size()&&k<tam.size()&&luu[x][j].fi>=tam[k].fi)||k>=tam.size())
      |                                                                              ~^~~~~~~~~~~~
bitaro.cpp:60: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]
   60 |                 if(k<tam.size()&&f[tam[k].se]!=cnt)
      |                    ~^~~~~~~~~~~
bitaro.cpp:87: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]
   87 |            for(i=0;i<luu[y].size();++i)
      |                    ~^~~~~~~~~~~~~~
bitaro.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for(j=0;j<v[i].size();++j)
      |                     ~^~~~~~~~~~~~

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