Submission #992602

#	Time	Username	Problem	Language	Result	Execution time	Memory
992602		vivkostov	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2071 ms	425936 KiB

bitaro

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,m,qu,a,b,x,y,used[200005],br[200005];
vector<int>v[200005],v1[200005],c;
void bfs(int beg)
{
    used[beg]=1;
    int w,nb;
    queue<int>q;
    q.push(beg);
    //cout<<beg<<endl;
    while(!q.empty())
    {
        w=q.front();
        q.pop();
        if(br[w])br[w]--;
        if(br[w])continue;
        for(int i=0; i<(int)(v[w].size()); i++)
        {
            nb=v[w][i];
            q.push(nb);
            used[nb]=used[w]+1;
        }
    }
}
void bfs1(int beg)
{
    used[beg]=1;
    int w,nb;
    queue<int>q;
    q.push(beg);
    while(!q.empty())
    {
        w=q.front();
        q.pop();
        for(int i=0; i<(int)(v[w].size()); i++)
        {
            nb=v[w][i];
            br[nb]++;
            if(!used[nb])
            {
                q.push(nb);
                used[nb]=used[w]+1;
            }
        }
    }
}
int dp[200005][505],par[200005],used1[200005],in[200005],used2[200005],from[200005][505],zan[200005],za,us[200005];
void go_up(int);
void make_dp(int);
void go_up(int beg)
{
    int w,br=0;
    used2[beg]=1;
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!used2[w]&&!used1[w])
        {
            go_up(w);
            br++;
        }
    }
    if(!br)make_dp(beg);
}
int get_up(int beg)
{
    int ii=0,br=0,w;
    for(int i=1; i<=500; i++)
    {
        for(int j=0; j<v[beg].size(); j++)
        {
            w=v[beg][j];
            //if(beg==7)cout<<beg<<" "<<w<<" "<<in[w]+1<<" "<<dp[w][in[w]+1]<<" "<<us[from[w][in[w]+1]]<<endl;
            while(us[from[w][in[w]+1]]&&from[w][in[w]+1]!=0)
            {
                //cout<<in[w]<<endl;
                in[w]++;
            }
            if(!us[from[w][in[w]+1]]&&dp[w][in[w]+1]&&dp[beg][i]<dp[w][in[w]+1]+1)
            {
                //if(beg==7)cout<<beg<<" "<<w<<" "<<in[w]+1<<" "<<dp[w][in[w]+1]<<endl;
                ii=w;
                dp[beg][i]=dp[w][in[w]+1]+1;
                from[beg][i]=from[w][in[w]+1];
            }
        }
        if(!ii)break;
        else br++;
        us[from[beg][i]]=1;
        in[ii]++;
        ii=0;
    }
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        in[w]=0;
    }
    //cout<<br<<endl;
    return br;
}
void make_new(int beg,int en)
{
    en++;
    int ten=en;
    int w;
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!us[w])
        {
            dp[beg][en]=1;
            from[beg][en]=w;
            en++;
        }
    }
    for(int i=1; i<en; i++)
    {
        us[from[beg][i]]=0;
    }
}
void make_dp(int beg)
{
    int w;
    for(int i=0; i<v[beg].size(); i++)
    {
        w=v[beg][i];
        if(!used1[w])
        {
            go_up(w);
            return;
        }
    }
    used1[beg]=1;
    int en=get_up(beg);
    make_new(beg,en);
    for(int i=0; i<v1[beg].size(); i++)
    {
        w=v1[beg][i];
        if(!used1[w])make_dp(w);
    }
}
void read()
{
    cin>>n>>m>>qu;
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b;
        v[b].push_back(a);
        v1[a].push_back(b);
    }
    us[0]=1;
    make_dp(1);
    /*for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=5; j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<i<<endl;
    }
    */
    for(int i=1; i<=qu; i++)
    {
        cin>>x>>y;
        for(int j=1; j<=y; j++)
        {
            int h;
            cin>>h;
            zan[h]=1;
            c.push_back(h);
        }
        if(y>300)
        {
            bfs1(x);
            memset(used,0,sizeof(used));
            bfs(x);
            int ma=-1,num=0;
            for(int j=1; j<=n; j++)
            {
                if(num==(int)(c.size())||j!=c[num])ma=max(ma,used[j]-1);
                else num++;
            }
            cout<<ma<<endl;
            memset(br,0,sizeof(br));
            memset(used,0,sizeof(used));
        }
        else
        {
            if(y==0)
            {
                cout<<dp[x][1]<<endl;
            }
            else
            {
                for(int j=1; j<=y; j++)
                {
                    if(!zan[from[x][j]])
                    {
                        if(from[x][j]==0&&zan[x])
                        {
                            cout<<-1<<endl;
                            break;
                        }
                        cout<<dp[x][j]<<endl;
                        break;
                    }
                    if(j==y)
                    {
                        if(from[x][j]==0&&zan[x])cout<<-1<<endl;
                        else if(from[x][j]==0)cout<<0<<endl;
                        else cout<<dp[x][j+1]<<endl;
                    }
                }
            }
        }
        for(int j=1; j<=y; j++)
        {
            zan[c[j-1]]=0;
        }
        memset(zan,0,sizeof(zan));
        c.clear();
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void go_up(int)':
bitaro.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0; i<v[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int get_up(int)':
bitaro.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j=0; j<v[beg].size(); j++)
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0; i<v[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'void make_new(int, int)':
bitaro.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0; i<v[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
bitaro.cpp:112:9: warning: unused variable 'ten' [-Wunused-variable]
  112 |     int ten=en;
      |         ^~~
bitaro.cpp: In function 'void make_dp(int)':
bitaro.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0; i<v[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~
bitaro.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for(int i=0; i<v1[beg].size(); i++)
      |                  ~^~~~~~~~~~~~~~~

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