Submission #567499

#	Time	Username	Problem	Language	Result	Execution time	Memory
567499		Abdulmohsen1284	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	303 ms	34496 KiB

bitaro

#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
priority_queue < pair <int, int> > pat[100005];
const int inf=1e9;
int num[100005],c[100005];
vector <int> tr[100005];
bool la[100005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n,m,q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++)
    {
        long long fr,sc;
        cin>>fr>>sc;
        if(fr<sc)
            swap(fr,sc);
        tr[sc].push_back(fr);
    }
    int sq=ceil((double)sqrt(q));
    sq++;
    if(sq>100)
    {
        sq/=18;
    }
    for(int i=1;i<=n;i++)
    {
        pat[i].push({0,i});
        //auto cur = pat[i].top();
        for(auto j : tr[i])
        {
            priority_queue < pair < int, int> > ne,ai,aj;
            ai=pat[i];
            aj=pat[j];
            while(ne.size()<sq)
            {
                
                //cout<<"chek1"<<endl;
                if(!ai.empty()&&!aj.empty())
                {
                    auto rn1=ai.top(),rn2=aj.top();
                    //cout<<"1"<<endl;
                    if(rn1.first<rn2.first)
                    {
                        ne.push(rn2);
                        aj.pop();
                    }
                    else
                    {
                        ne.push({rn1.first+1,rn1.second});
                        ai.pop();
                    }
                }
                else if(!ai.empty())
                {
                    //cout<<"2"<<endl;
                    auto rn1=ai.top();
                    ne.push({rn1.first+1,rn1.second});
                    ai.pop();
                }
                else if(!aj.empty())
                {
                    //cout<<"3"<<endl;
                    auto rn2=aj.top();
                    ne.push(rn2);
                    aj.pop();
                }
                else{
                    //cout<<"4"<<endl;
                    break;
                }
                //cout<<"HI"<<endl;
            }
            pat[j]=ne;
        }
    }
    for(int i=0;i<q;i++)
    {
        long long t,y;
        cin>>t>>y;
        if(y>=sq)
        {
            //cout<<"hell ye ";
            for(int j=0;j<y;j++)
            {
                long long bad;
                cin>>bad;
                num[bad]=-inf;
            }
            for(int j=1;j<=n;j++)
            {
                for(auto k : tr[j])
                {
                    num[k]=max(num[k],num[j]+1);
                }
            }
            cout<<max(-1,num[t])<<"\n";
            for(int j=1;j<=n;j++)
                num[j]=0;
        }
        else
        {
            //cout<<"yo ";
            for(int j=0;j<y;j++)
            {
                cin>>c[i];
                la[c[i]]=true;
            }
            int ans=-1;
            auto rn = pat[t];
            while(!rn.empty())
            {
                auto here = rn.top();
                rn.pop();
                //cout<<here.second<<" ";
                if(!la[here.second])
                    ans=max(ans,here.first);
            }
            for(int j=0;j<y;j++)
            {
                la[c[i]]=false;
            }
            cout<<ans<<"\n";
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:44:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |             while(ne.size()<sq)
      |                   ~~~~~~~~~^~~

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