Submission #1209876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209876		Younis_Dwai	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2095 ms	6764 KiB

bitaro

#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define popf pop_frot
#define popb pop_back
//#define int long long
#define in insert
#define mid (l+r)/2
//register int cnt
using namespace std;
const int N=1e5+5;
const int sqr=500;
vector<int> adj[N];
int vis[N];
struct loin{
       pair<int,int> b[501];
};
loin combine(loin &x , loin &y){
     loin ret;
     int id1=1,id2=1,skip=0;
     while(id1+id2-2-skip<sqr){
           //cout<<" @ "<<id1<<' '<<id2<<' '<<skip<<endl;
           if(id1<=sqr && vis[x.b[id1].S]==1){
              ++id1;
              ++skip;
              continue ;
           }
           else if(id2<=sqr && vis[y.b[id2].S]==1){
              ++id2;
              ++skip;
              continue ;
           }
           if(id2==sqr+1 || (y.b[id2].S==0 && x.b[id1].S!=0)){
                 ret.b[id1+id2-1]=x.b[id1];
                if(x.b[id1].S!=0) vis[x.b[id1].S]=1;
                id1++;
           }
           else if(id1==sqr+1 || (x.b[id1].S==0 && y.b[id2].S!=0)){
                ret.b[id1+id2-1].F=y.b[id2].F+1;
                ret.b[id1+id2-1].S=y.b[id2].S;
                if(y.b[id2].S!=0) vis[y.b[id2].S]=1;
                id2++;
           }
           else if(x.b[id1].F>=y.b[id2].F+1){
                ret.b[id1+id2-1]=x.b[id1];
                if(x.b[id1].S!=0) vis[x.b[id1].S]=1;
                id1++;
           }
           else{
                ret.b[id1+id2-1].F=y.b[id2].F+1;
                ret.b[id1+id2-1].S=y.b[id2].S;
                if(y.b[id2].S!=0) vis[y.b[id2].S]=1;
                id2++;
           }
           //cout<<" @ "<<id1<<' '<<id2<<' '<<skip<<endl;
     }
     for(int i=1;i<=sqr;i++){
         vis[x.b[i].S]=vis[y.b[i].S]=0;
     }
     //cout<<" @ "<<' ';
     for(int j=1;j<=sqr;j++){
         if(ret.b[j].S==0) break ;
         //cout<<ret.b[j].F<<' ';
     }
     //cout<<endl;
     return ret;
}
int n,m,Q,busy[N],d[N];
loin best[N];
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr);
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=sqr;j++){
            best[i].b[j]={0,0};
        }
    }
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        adj[y].pb(x);
    }
    loin cur;
    for(int j=1;j<=sqr;j++) cur.b[j]={-1,0};
    for(int i=1;i<=n;i++){
        best[i].b[1]={0,i};
        for(auto u : adj[i]){
           //cout<<" # "<<i<<' '<<u<<endl;
           cur.b[1]={-1,u};
           loin z=combine(best[u],cur);
           best[i]=combine(best[i],z);
        }
    }
    busy[0]=1;
    while(Q--){
          int node,cnt;cin>>node>>cnt;
          vector<int> v;
          for(int i=1;i<=cnt;i++){
              int x;cin>>x;
              v.pb(x);
              busy[x]=1;
          }
          if(cnt<sqr){
             int ret=-1;
             for(int i=1;i<=sqr;i++){
                 if(busy[best[node].b[i].S]==0){
                    ret=max(ret,best[node].b[i].F);
                 }
             }
             cout<<ret<<endl;
          }
          else{
             queue<int> q;
             for(int i=1;i<=n;i++) d[i]=0;
             q.push(node);
             while(!q.empty()){
                   int node=q.front();
                   for(auto u : adj[node]){
                       if(d[u]<d[node]+1){
                          d[u]=1+d[node];
                          q.push(u);
                       }
                   }
             }
             int ret=-1;
             for(int i=1;i<=node;i++){
                 if(busy[i]) continue ;
                 ret=max(ret,d[i]);
             }
             cout<<ret<<endl;
          }
          for(auto u : v){
              busy[u]=0;
          }
    }
    return 0;
}

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