Submission #546480

#	Time	Username	Problem	Language	Result	Execution time	Memory
546480		stefantaga	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	5 ms	7380 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++)
    {
        dist[i].push_back({i,-1});
        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;
            vector <pair <int,int>> acum;
            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;
                }
                if (dist[i][st].second>dist[i][dr].second)
                {
                    fr[dist[i][st].first]=1;
                    acum.push_back({dist[i][st].first,dist[i][st].second+1});
                    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+1});
                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++;
            }
            dist[i]=acum;
            acum.clear();
        }
    }
    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]>solfin)
                {
                    solfin=distfin[j];
                }
            }
            cout<<solfin-1<<'\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=dist[nod][j].second;
                    break;
                }
            }
            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:68: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]
   68 |             while (acum.size()<bucket&&st<dist[i].size())
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:68: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]
   68 |             while (acum.size()<bucket&&st<dist[i].size())
      |                                        ~~^~~~~~~~~~~~~~~
bitaro.cpp:78: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]
   78 |             while (acum.size()<bucket&&dr<dist[nod].size())
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:78: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]
   78 |             while (acum.size()<bucket&&dr<dist[nod].size())
      |                                        ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:119:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |                 for (int j =0;j<inv[acum].size();j++)
      |                               ~^~~~~~~~~~~~~~~~~
bitaro.cpp:142: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]
  142 |             for (int j=0;j<dist[nod].size();j++)
      |                          ~^~~~~~~~~~~~~~~~~

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