Submission #537202

#	Time	Username	Problem	Language	Result	Execution time	Memory
537202		fadi57	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	15 ms	24176 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
const int mx=500000;
const int mx2=2e4+19;
typedef long long ll;
const int mod=998244353 ;
const int SQ=350;
const ll inf=1e9+10;
int n,m,q;
vector<int>adj[mx]; vector <pair <int, int>>f[mx];int vis[mx];int vis2[mx];int cur=1;int dp[mx];
vector< pair<int,int>> merge(vector< pair < int ,int > > &l, vector< pair < int,int > >&r){
    int left=0;  int right=0;   int lsize=l.size();  int rsize=r.size();
   vector<pair<int,int>>ret;

   while(ret.size()<SQ&&(left<lsize||right<rsize)){

      pair<int,int>ok;
      if(left==lsize){
        ok=r[right];
         ok.first++;
         right++;

      }else if(right==rsize){
            ok=l[left];

            left++;
      }else if(l[left].first>r[right].first+1){
            ok=l[left];
            left++;
      }else{
      ok=r[right];
      right++;
       ok.first++;
      }
      if(vis[ok.second]==cur){continue;}
      vis[ok.second]=cur;
      ret.push_back(ok);

    }
    return ret;
   }

 int main(){


    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
            int x,y;cin>>x>>y;
            adj[y].push_back(x);
    }

   for(int i=1;i<=n;i++){
     f[i].push_back({0,i});

       for(auto&j:adj[i]){
            f[i] = merge(f[i], f[j]);
      cur++;
        }

    }
    /*
     cout<<"TEST \n";
    for(auto it:f[4]){
         cout<<it.second<<" "<<it.first<<endl;
        }
        cout<<endl;
        */
   while(q--){
      int idx,y;
      cin>>idx>>y;
      int arr[y];
     for(int j=0;j<y;j++){
            cin>>arr[j];

        vis2[arr[j]]=1;
     }
     if(y<SQ){
            int ans=-1;
               for(auto it:f[idx]){
                    if(vis2[it.second]){continue;}
                ans=max(ans,it.first);
                break;
               }
               cout<<ans<<"\n";
     }else{
         int ans=-1;
         vector<int>dis(idx+1,-1);
         dis[idx]=0;

         for(int j=idx;j>=1;j--){
            for(auto it:adj[j]){
                dis[it]=max(dis[it],dis[j]+1);
            }
            if(vis2[j]){}else{ ans=max(ans,dis[j]); }
         }
         cout<<ans<<"\n";
       }
     for(int j=0;j<y;j++){


        vis2[arr[j]]=0;
     }

   }

}

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