Submission #1112144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112144		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1382 ms	299388 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define all(x) x.begin(),x.end()
//#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

const ll maxn=2e5+69;
const ll offset=2e5;
const ll inf=1e9;
const int base=350;
const ll mod=1e9+7;

vector<int> adj[maxn],adj_r[maxn];
vector<pii> Lx,L[maxn];
bool dd[maxn];
int n,m,q;
int deg[maxn];
queue<int> Q;
int x[maxn],dep[maxn];
void Merge(vector<pii>& Lu,vector<pii> Lv,bool debug=0)
{
    for(pii& x:Lv) x.fi++;
    int i=0,j=0;
    Lx.clear();
    while (i<Lu.size() || j<Lv.size())
    {
        if (j==Lv.size())
        {
            if (!dd[Lu[i].se] && Lx.size()<base)
            {
                Lx.pb(Lu[i]);
                dd[Lu[i].se]=1;
            }
            i++;
        }
        else if (i==Lu.size() || Lu[i]<Lv[j])
        {
            if (!dd[Lv[j].se] && Lx.size()<base)
            {
                Lx.pb(Lv[j]);
                dd[Lv[j].se]=1;
            }
            j++;
        }
        else
        {
            if (!dd[Lu[i].se] && Lx.size()<base)
            {
                Lx.pb(Lu[i]);
                dd[Lu[i].se]=1;
            }
            i++;
        }
    }
    Lu=Lx;
    for(pii x:Lu) dd[x.se]=0;
}
void dfs_dag()
{
    for1(u,1,n) deg[u]=adj_r[u].size();
    for1(u,1,n) if (!deg[u]) Q.push(u);
    for1(u,1,n) dep[u]=0;
    for1(u,1,n) if (dd[u]) dep[u]=-inf;
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
//        cerr<< u<< ' '<<dep[u]<<'\n';
        for(int v:adj[u])
        {
            dep[v]=max(dep[v],dep[u]+1);
            deg[v]--;
            if (!deg[v]) Q.push(v);
        }
    }
}
void sol()
{
    cin >> n>> m>> q;
    for1(i,1,m)
    {
        int u,v;cin >> u>>v;
        adj[u].pb(v);
        adj_r[v].pb(u);
    }
    for1(u,1,n) deg[u]=adj_r[u].size();
    for1(u,1,n) if (!deg[u]) Q.push(u);
    while (!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        L[u].pb({0,u});
        for(int v: adj_r[u])
        {
            Merge(L[u],L[v]);
        }
        for(int v:adj[u])
        {
            deg[v]--;
            if (!deg[v]) Q.push(v);
        }
    }
//    for1(u,1,n)
//    {
//        cerr<<"list "<<u<<":\n";
//        for(pii v:L[u]) cerr<<v.se<<' '<<v.fi<<'\n';
//        cerr<<'\n';
//    }
    for1(i,1,q)
    {
        int u,nn;cin >>u>> nn;
        for1(i,1,nn)
        {
            cin >> x[i];
            dd[x[i]]=1;
        }
        int res=-1;
        if (nn<base)
        {
            for(pii x:L[u])
            {
                if (!dd[x.se])
                {
                    res=x.fi;
                    break;
                }
            }
            cout << res<<'\n';
        }
        else
        {
            dfs_dag();
//            cerr<< "ac\n";
            if (dep[u]<0) cout << "-1\n";
            else cout << dep[u]<<'\n';
        }
        for1(i,1,nn) dd[x[i]]=0;
    }

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("aacd.inp","r",stdin);
//    freopen("aacd.out","w",stdout);

    int t=1;//cin >> t;
    for1(i,1,t) {
//        cout << "Case #"<<i<<": ";
        sol();
    }
}

/*
5 6 1
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1




*/

Compilation message (stderr)

bitaro.cpp: In function 'void Merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >, bool)':
bitaro.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (i<Lu.size() || j<Lv.size())
      |            ~^~~~~~~~~~
bitaro.cpp:35:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (i<Lu.size() || j<Lv.size())
      |                           ~^~~~~~~~~~
bitaro.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (j==Lv.size())
      |             ~^~~~~~~~~~~
bitaro.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         else if (i==Lu.size() || Lu[i]<Lv[j])
      |                  ~^~~~~~~~~~~

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