Submission #991930

#	Time	Username	Problem	Language	Result	Execution time	Memory
991930		simona1230	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1468 ms	347472 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
const int s=315;

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];

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

deque<pair<int,int> > merge_(deque<pair<int,int> > d1,deque<pair<int,int> > d2,int add)// 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+add)
        {
            d.push_front(d1[i]);
            i--;
        }
        else
        {
            //cout<<"- "<<endl;
            d.push_front({d2[j].first,d2[j].second+add});
            j--;
        }
        //cout<<i<<" "<<j<<endl;
    }

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

    return d;
}

void prec()
{
    for(int i=1;i<=n;i++)
    {
        p[i]=merge_(p[i],{{i,0}},0);
        for(int j=0;j<v[i].size();j++)
        {
            int nb=v[i][j];
            p[nb]=merge_(p[nb],p[i],1);
        }
        /*cout<<i<<" ";
        for(int j=0;j<p[i].size();j++)
            cout<<p[i][j].first<<", "<<p[i][j].second<<endl;*/
    }
}

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> >, int)':
bitaro.cpp:39:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   39 |         if(j==-1||i!=-1&&d1[i].second>d2[j].second+add)
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void prec()':
bitaro.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(int x=0; x<v[j].size(); x++)
      |                              ~^~~~~~~~~~~~
bitaro.cpp:105: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]
  105 |             for(int j=0; j<p[t].size(); j++)
      |                          ~^~~~~~~~~~~~

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