Submission #991974

#	Time	Username	Problem	Language	Result	Execution time	Memory
991974		simona1230	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1872 ms	400212 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
const int s=350;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n,m,q;
vector<int> v[100001];
void read()
{
    cin>>n>>m>>q;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
}

int dp[100001];
int f[100001];
int used[100001];

deque <pair<int,int> > p[100001];

deque<pair<int,int> > merge_(deque<pair<int,int> > d1,deque<pair<int,int> > d2)// d2+1
{
    deque<pair<int,int> > d;
    int i=d1.size()-1;
    int j=d2.size()-1;
    while(d.size()<=s&&(i>=0||j>=0))
    {
        //cout<<i<<" "<<j<<endl;
        if(j==-1||i!=-1&&d1[i].second>=d2[j].second+1)
        {
            if(used[d1[i].first])
                {
                    i--;
                    continue;
                }
            d.push_front(d1[i]);
            used[d1[i].first]=1;
            i--;
        }
        else
        {
            if(used[d2[j].first])
            {
                j--;
                continue;
            }
            //cout<<"- "<<endl;
            d.push_front({d2[j].first,d2[j].second+1});
            used[d2[j].first]=1;
            j--;
        }
        //cout<<i<<" "<<j<<endl;
    }

    for(int i=0;i<d.size();i++)
        used[d[i].first]=0;

    //cout<<"out"<<endl;

    return d;
}

void prec()
{
    for(int i=1;i<=n;i++)
    {
        p[i]=merge_(p[i],{{i,-1}});
        for(int j=0;j<v[i].size();j++)
        {
            int nb=v[i][j];
            p[nb]=merge_(p[nb],p[i]);
        }
    }
}

void solve()
{
    for(int i=1; i<=q; i++)
    {
        int t,k;
        cin>>t>>k;

        for(int j=1; j<=k; j++)
        {
            int x;
            cin>>x;
            f[x]=i;
        }

        if(k>s)
        {
            for(int j=1; j<=n; j++)
                dp[j]=-1;

            for(int j=1; j<=n; j++)
            {
                if(f[j]!=i)dp[j]=max(dp[j],0);
                for(int x=0; x<v[j].size(); x++)
                    if(dp[j]!=-1)dp[v[j][x]]=max(dp[v[j][x]],dp[j]+1);
            }

            cout<<dp[t]<<endl;
        }
        else
        {
            int ans=-1;
            for(int j=0; j<p[t].size(); j++)
            {
                if(f[p[t][j].first]!=i)
                    ans=max(ans,p[t][j].second);
            }
            cout<<ans<<endl;
        }
    }
}

int main()
{
    speed();
    read();
    prec();
    solve();
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::deque<std::pair<int, int> > merge_(std::deque<std::pair<int, int> >, std::deque<std::pair<int, int> >)':
bitaro.cpp:40:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |         if(j==-1||i!=-1&&d1[i].second>=d2[j].second+1)
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=0;i<d.size();i++)
      |                 ~^~~~~~~~~
bitaro.cpp: In function 'void prec()':
bitaro.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:109:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                 for(int x=0; x<v[j].size(); x++)
      |                              ~^~~~~~~~~~~~
bitaro.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for(int j=0; j<p[t].size(); j++)
      |                          ~^~~~~~~~~~~~

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