Submission #707864

#	Time	Username	Problem	Language	Result	Execution time	Memory
707864		ToroTN	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1314 ms	415168 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first 
#define Y second
int n,m,t,u_i,v_i,num,ban[100005],root=sqrt(100000),dp[100005];
int hsh[100005],party,hsh2[100005],ans;
int bug,bug2;
vector<int> from[100005];
vector<pair<int,int> > best[100005];
vector<pair<int,int> > merge(vector<pair<int,int> > v1,vector<pair<int,int> > v2)
{
    /*if(bug==6&&bug2==5)
    {
        printf("v1\n");
        for(int i=0;i<v1.size();i++)
        {
            printf("%d %d\n",v1[i].X,v1[i].Y);
        }
        printf("\n");
        printf("v2\n");
        for(int i=0;i<v2.size();i++)
        {
            printf("%d %d\n",v2[i],v2[i].Y);
        }
        printf("\n");
    }*/
    // printf("v1\n");
    // for(int i=0;i<v1.size();i++)
    // {
    //     printf("%d %d\n",v1[i].X,v1[i].Y);
    // }
    // printf("\n");
    // printf("v2\n");
    // for(int i=0;i<v2.size();i++)
    // {
    //     printf("%d %d\n",v2[i],v2[i].Y);
    // }
    // printf("\n");
    vector<pair<int,int> > v;
    int it1=0,it2=0,it=0;
    while(1)
    {
        if(v.size()==root+1)break;
        if(it1==v1.size()&&it2==v2.size())break;
        if(it1==v1.size())
        {
            if(hsh2[v2[it2].Y]==0)
            {
                hsh2[v2[it2].Y]=1;
                v.pb({v2[it2].X+1,v2[it2].Y});
            }
            ++it2;
        }else if(it2==v2.size())
        {
            if(hsh2[v1[it1].Y]==0)
            {
                hsh2[v1[it1].Y]=1;
                v.pb(v1[it1]);
            }
            ++it1;
        }else
        {
            if(v1[it1].X>v2[it2].X+1)
            {
                if(hsh2[v1[it1].Y]==0)
                {
                    hsh2[v1[it1].Y]=1;
                    v.pb(v1[it1]);
                }
                ++it1;
            }else
            {
                if(hsh2[v2[it2].Y]==0)
                {
                    hsh2[v2[it2].Y]=1;
                    v.pb({v2[it2].X+1,v2[it2].Y});
                }
                ++it2;
            }
        }
        ++it;
    }
    for(int i=0;i<v1.size();i++)hsh2[v1[i].Y]=0;
    for(int i=0;i<v2.size();i++)hsh2[v2[i].Y]=0;
    /*if(bug==6&&bug2==5)
    {
        printf("vvv\n");
        for(int i=0;i<v.size();i++)
        {
            printf("%d %d\n",v[i].X,v[i].Y);
        }
    }*/
    /*printf("vvv\n");
    for(int i=0;i<v.size();i++)
    {
        printf("%d %d\n",v[i].X,v[i].Y);
    }*/
    return v;
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    //root=-1;
    cin >> n >> m >> t;
    for(int i=1;i<=m;i++)
    {
        cin >> u_i >> v_i;
        from[v_i].pb(u_i);
    }
    for(int i=1;i<=n;i++)
    {
        //printf("iiiiiiiiiiii=%d\n",i);
        best[i].pb({0,i});
        for(auto node:from[i])
        {
            //printf("node=%d\n",node);
            bug=i;
            bug2=node;
            best[i]=merge(best[i],best[node]);
            /*if(i==6)
            {
                printf("node=%d\n",node);
                for(int j=0;j<best[i].size();j++)
                {
                    printf("%d %d\n",best[i][j].X,best[i][j].Y);
                }
            }*/
        }
    }
    /*for(int i=1;i<=n;i++)   
    {
        printf("i=%d\n",i);
        for(int j=0;j<best[i].size();j++)
        {
            printf("%d %d\n",best[i][j].X,best[i][j].Y);
        }
    }*/
    while(t--)
    {
        cin >> party >> num;
        for(int i=1;i<=num;i++)
        {
            cin >> ban[i];
            hsh[ban[i]]=1;
        }
        /*for(int i=1;i<=n;i++)
        {
            printf("%d ",hsh[i]);
        }
        printf("\n");*/
        if(num>root)
        {
            for(int i=1;i<=n;i++)
            {
                dp[i]=-1e9;
                if(hsh[i]==0)dp[i]=0;
                for(auto node:from[i])
                {
                    dp[i]=max(dp[i],dp[node]+1);
                }
            }
            if(dp[party]<0)
            {
                printf("-1\n");
            }else
            {
                printf("%d\n",dp[party]);
            }
        }else
        {
            ans=-1e9;
            for(int i=0;i<best[party].size();i++)
            {
                if(hsh[best[party][i].Y]==0)
                {
                    ans=max(ans,best[party][i].X);
                }
            }
            /*for(int i=0;i<best[party].size();i++)
            {
                printf("%d %d\n",best[party][i].X,best[party][i].Y);
            }*/
            if(ans==-1e9)
            {
                printf("-1\n");
            }else
            {
                printf("%d\n",ans);
            }
        }
        for(int i=1;i<=num;i++)
        {
            hsh[ban[i]]=0;
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:44:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if(v.size()==root+1)break;
      |            ~~~~~~~~^~~~~~~~
bitaro.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(it1==v1.size()&&it2==v2.size())break;
      |            ~~~^~~~~~~~~~~
bitaro.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(it1==v1.size()&&it2==v2.size())break;
      |                            ~~~^~~~~~~~~~~
bitaro.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(it1==v1.size())
      |            ~~~^~~~~~~~~~~
bitaro.cpp:54: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]
   54 |         }else if(it2==v2.size())
      |                  ~~~^~~~~~~~~~~
bitaro.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<v1.size();i++)hsh2[v1[i].Y]=0;
      |                 ~^~~~~~~~~~
bitaro.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<v2.size();i++)hsh2[v2[i].Y]=0;
      |                 ~^~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:173:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |             for(int i=0;i<best[party].size();i++)
      |                         ~^~~~~~~~~~~~~~~~~~~

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