제출 #537181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537181		fadi57	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	21 ms	23888 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];
            ok.first++;
            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});
     dp[i]=0;
       for(auto&j:adj[i]){
            f[i] = merge(f[i], f[j]);
            dp[i]=max(dp[i],dp[j]+1);
        }
        cur++;
    }
   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:adj[idx]){
                    if(vis2[it]){continue;}
                ans=max(ans,dp[it]+1);
               }
               cout<<ans;
     }else{
         int ans=-1;
         vector<int>dis(idx+1,-1);
         dis[idx]=0;
         //cout<<"TESR \n";
        // cout<<idx<<endl;
         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