Submission #546498

#	Time	Username	Problem	Language	Result	Execution time	Memory
546498		stefantaga	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2093 ms	248500 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;
pair <int,int >  dist[100005][305];
int mar[100005];
pair <int,int> acum[305];
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++)
    {
        int numar=0;
        for (int j=0;j<inv[i].size();j++)
        {
            int nod = inv[i][j];
            for (int k=1;k<=mar[i];k++)
            {
                fr[dist[i][k].first]=0;
            }
            for (int k=1;k<=mar[nod];k++)
            {
                fr[dist[nod][k].first]=0;
            }
            int st = 0 ,dr=0;
            while (numar<bucket&&st<=mar[i]&&dr<=mar[nod])
            {
                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[++numar]={dist[i][st].first,dist[i][st].second};
                    st++;
                }
                else
                {
                    fr[dist[nod][dr].first]=1;
                    acum[++numar]={dist[nod][dr].first,dist[nod][dr].second+1};
                    dr++;
                }
            }
            while (numar<bucket&&st<=mar[i])
            {
                 if (fr[dist[i][st].first]==1)
                {
                    st++;
                    continue;
                }
                acum[++numar]={dist[i][st].first,dist[i][st].second};
                st++;
            }
            while (numar<bucket&&dr<=mar[nod])
            {
                if (fr[dist[nod][dr].first]==1)
                {
                    dr++;
                    continue;
                }
                acum[++numar]={dist[nod][dr].first,dist[nod][dr].second+1};
                dr++;
            }
            mar[i]=numar;
            for (int tk=1;tk<=numar;tk++)
            {
                dist[i][tk]=acum[tk];
            }
        }
        if (mar[i]<bucket)
        {
            dist[i][++mar[i]]={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=1;j<=mar[nod];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:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int j=0;j<inv[i].size();j++)
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp:57:32: warning: variable 'stanga' set but not used [-Wunused-but-set-variable]
   57 |                 pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
      |                                ^~~~~~
bitaro.cpp:57:53: warning: variable 'dreapta' set but not used [-Wunused-but-set-variable]
   57 |                 pair <int,int> stanga = dist[i][st],dreapta = dist[nod][dr];
      |                                                     ^~~~~~~
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++)
      |                               ~^~~~~~~~~~~~~~~~~

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