Submission #754450

#	Time	Username	Problem	Language	Result	Execution time	Memory
754450		Valters07	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1218 ms	524288 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e5+5;
const ll B = sqrt(N)+2;
vector<ll> g[N];
vector<pair<ll,ll> > best[N];
ll dist[N];
bool dupl[N];
void merg_sort(vector<pair<ll,ll> > &a, vector<pair<ll,ll> > b)
{
    for(auto &x:b)
        x.fi++,
        dupl[x.se]=1;
    vector<pair<ll,ll> > nw, nwa;
    for(auto x:a)
        if(!dupl[x.se])
            nwa.pb(x);
    swap(a,nwa);
    for(auto x:b)
        dupl[x.se]=0;
    ll it = 0, it2 = 0;
    while((it<a.size()||it2<b.size())&&nw.size()<=B)
    {
        if(it>=a.size())
            nw.pb(b[it2++]);
        else if(it2>=b.size())
            nw.pb(a[it++]);
        else if(a[it]>b[it2])
            nw.pb(a[it++]);
        else
            nw.pb(b[it2++]);
    }
    swap(a,nw);
}
int main()
{
    fio
//    ifstream cin("in.in");
    ll n, m, q;
    cin >> n >> m >> q;
    while(m--)
    {
        ll u, v;
        cin >> u >> v;
        g[u].pb(v);
    }
    for(ll i = 1;i<=n;i++)
        best[i].pb({0,i});
    for(ll i = 1;i<=n;i++)
        for(auto j:g[i])
            merg_sort(best[j],best[i]);
    while(q--)
    {
        ll f, y;
        cin >> f >> y;
        vector<ll> del(y);
        for(auto &x:del)
            cin >> x;
        if(y<B)
        {
            for(auto x:del)
                dupl[x]=1;
            ll it = 0;
            while(it<best[f].size()&&dupl[best[f][it].se])
                it++;
            if(it>=best[f].size())
                cout << -1;
            else
                cout << best[f][it].fi;
            for(auto x:del)
                dupl[x]=0;
        }
        else
        {
            for(auto x:del)
                dist[x]=-1e9;
            for(ll i = 1;i<=n;i++)
                for(auto j:g[i])
                    dist[j]=max(dist[j],dist[i]+1);
            if(dist[f]<0)
                cout << -1;
            else
                cout << dist[f];
            for(ll i = 1;i<=n;i++)
                dist[i]=0;
        }
        cout << "\n";
    }
//    cin.close();
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void merg_sort(std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >)':
bitaro.cpp:31:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while((it<a.size()||it2<b.size())&&nw.size()<=B)
      |            ~~^~~~~~~~~
bitaro.cpp:31:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while((it<a.size()||it2<b.size())&&nw.size()<=B)
      |                         ~~~^~~~~~~~~
bitaro.cpp:33:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if(it>=a.size())
      |            ~~^~~~~~~~~~
bitaro.cpp:35:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         else if(it2>=b.size())
      |                 ~~~^~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:73:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while(it<best[f].size()&&dupl[best[f][it].se])
      |                   ~~^~~~~~~~~~~~~~~
bitaro.cpp:75:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             if(it>=best[f].size())
      |                ~~^~~~~~~~~~~~~~~~

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