Submission #546494

#	Time	Username	Problem	Language	Result	Execution time	Memory
546494		stefantaga	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2095 ms	260580 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
vector <int> v[100005],inv[100005];
int n,m,q,i,fr[100005],val[100005],distfin[100005],teste;
vector <pair <int,int > > dist[100005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m>>teste;
    for (i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if (x>y)
        {
            swap(x,y);
        }
        inv[y].push_back(x);
    }
    int bucket = sqrt(n);
    for (i=1;i<=n;i++)
    {
        vector <pair <int,int>> acum;
        for (int j=0;j<inv[i].size();j++)
        {
            int nod = inv[i][j];
            for (int k=0;k<dist[i].size();k++)
            {
                fr[dist[i][k].first]=0;
            }
            for (int k=0;k<dist[nod].size();k++)
            {
                fr[dist[nod][k].first]=0;
            }
            int st = 0 ,dr=0;
            acum.clear();
            while (acum.size()<bucket&&st<dist[i].size()&&dr<dist[nod].size())
            {
                if (fr[dist[i][st].first]==1)
                {
                    st++;
                    continue;
                }
                if (fr[dist[nod][dr].first]==1)
                {
                    dr++;
                    continue;
                }
                pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
                if (dist[i][st].second>=dist[nod][dr].second+1)
                {
                    fr[dist[i][st].first]=1;
                    acum.push_back({dist[i][st].first,dist[i][st].second});
                    st++;
                }
                else
                {
                    fr[dist[nod][dr].first]=1;
                    acum.push_back({dist[nod][dr].first,dist[nod][dr].second+1});
                    dr++;
                }
            }
            while (acum.size()<bucket&&st<dist[i].size())
            {
                 if (fr[dist[i][st].first]==1)
                {
                    st++;
                    continue;
                }
                acum.push_back({dist[i][st].first,dist[i][st].second});
                st++;
            }
            while (acum.size()<bucket&&dr<dist[nod].size())
            {
                if (fr[dist[nod][dr].first]==1)
                {
                    dr++;
                    continue;
                }
                acum.push_back({dist[nod][dr].first,dist[nod][dr].second+1});
                dr++;
            }
            for (int k=0;k<dist[i].size();k++)
            {
                fr[dist[i][k].first]=0;
            }
            for (int k=0;k<dist[nod].size();k++)
            {
                fr[dist[nod][k].first]=0;
            }
            dist[i]=acum;
        }
        if (dist[i].size()<bucket)
        dist[i].push_back({i,0});
    }
    for (i=1;i<=n;i++)
    {
        fr[i]=0;
    }
    for (;teste--;)
    {
        int nod,nr;
        cin>>nod >> nr;
        for (i=1;i<=nr;i++)
        {
            cin>>val[i];
            fr[val[i]]=1;
        }

        if (nr>=bucket)
        {
            queue <int> q;
            for (int j=1;j<=n;j++)
            {
                distfin[j]=0;
            }
            distfin[nod]=1;
            q.push(nod);
            while (!q.empty())
            {
                int acum = q.front();
                q.pop();
                for (int j =0;j<inv[acum].size();j++)
                {
                    int nod2 =  inv[acum][j];
                    if (distfin[nod2]<distfin[acum]+1)
                    {
                        distfin[nod2]=distfin[acum]+1;
                        q.push(nod2);
                    }
                }
            }
            int solfin = -1;
            for (int j=1;j<=n;j++)
            {
                if (fr[j]==0&&distfin[j]-1>solfin)
                {
                    solfin=distfin[j]-1;
                }
            }
            cout<<solfin<<'\n';
        }
        else
        {
            int solfin=-1;
            for (int j=0;j<dist[nod].size();j++)
            {
                int nod2 = dist[nod][j].first;
                if (fr[nod2]==0)
                {
                    solfin=max(solfin,dist[nod][j].second);
                }
            }
            cout<<solfin<<'\n';
        }
        for (i=1;i<=nr;i++)
        {
            fr[val[i]]=0;
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j=0;j<inv[i].size();j++)
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int k=0;k<dist[i].size();k++)
      |                          ~^~~~~~~~~~~~~~~
bitaro.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int k=0;k<dist[nod].size();k++)
      |                          ~^~~~~~~~~~~~~~~~~
bitaro.cpp:43:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |             while (acum.size()<bucket&&st<dist[i].size()&&dr<dist[nod].size())
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:43:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while (acum.size()<bucket&&st<dist[i].size()&&dr<dist[nod].size())
      |                                        ~~^~~~~~~~~~~~~~~
bitaro.cpp:43:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while (acum.size()<bucket&&st<dist[i].size()&&dr<dist[nod].size())
      |                                                           ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:55:32: warning: variable 'stanga' set but not used [-Wunused-but-set-variable]
   55 |                 pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
      |                                ^~~~~~
bitaro.cpp:55:53: warning: variable 'dreapta' set but not used [-Wunused-but-set-variable]
   55 |                 pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
      |                                                     ^~~~~~~
bitaro.cpp:69:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |             while (acum.size()<bucket&&st<dist[i].size())
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:69:42: 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 (acum.size()<bucket&&st<dist[i].size())
      |                                        ~~^~~~~~~~~~~~~~~
bitaro.cpp:79:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |             while (acum.size()<bucket&&dr<dist[nod].size())
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:79:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             while (acum.size()<bucket&&dr<dist[nod].size())
      |                                        ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for (int k=0;k<dist[i].size();k++)
      |                          ~^~~~~~~~~~~~~~~
bitaro.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for (int k=0;k<dist[nod].size();k++)
      |                          ~^~~~~~~~~~~~~~~~~
bitaro.cpp:99:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         if (dist[i].size()<bucket)
      |             ~~~~~~~~~~~~~~^~~~~~~
bitaro.cpp:129:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 for (int j =0;j<inv[acum].size();j++)
      |                               ~^~~~~~~~~~~~~~~~~
bitaro.cpp:152:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             for (int j=0;j<dist[nod].size();j++)
      |                          ~^~~~~~~~~~~~~~~~~

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