제출 #1209901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209901		Younis_Dwai	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	6 ms	6032 KiB

bitaro

#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=101;
vector<int> adj[N];
int n,m,Q,busy[N],d[N],vis[N],largest[N],c[N];
vector<pair<int,int>> 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<=m;i++){
        int x,y;cin>>x>>y;
        adj[y].pb(x);
    }
    memset(largest,-1,sizeof largest);
    for(int i=1;i<=n;i++){
        best[i].pb({0,i});
        vector<int> reach;
        for(auto u : adj[i]){
            for(auto[dis , from] : best[u]){
                if(largest[from]==-1){
                  reach.pb(from);
                  largest[from]=1+dis;
                  vis[from]=1;
                }
                else{
                  largest[from]=max(1+dis,largest[from]);
                }
            }
        }
        for(auto u : reach){
            best[i].pb({largest[u],u});
            largest[u]=-1;
        }
        sort(best[i].rbegin(),best[i].rend());
        while(best[i].size()>sqr) best[i].pop_back();
    }
    busy[0]=1;
    while(Q--){
          int node,cnt;cin>>node>>cnt;
          vector<int> v;
          for(int i=1;i<=cnt;i++){
              cin>>c[i];
              busy[c[i]]=1;
          }
          if(cnt<sqr){
              int ret=-1;
              for(auto u : best[node]){
                  if(busy[u.S]==0){
                     ret=u.F;
                     break ;
                  }
              }
              cout<<ret<<endl;
          }
          else{

             for(int i=1;i<=node;i++) d[i]=-1;
             d[node]=0;
             for(int i=node;i>=1;i--){
                 if(d[i]==-1) continue ;
                 for(auto u : adj[i]){
                     if(d[u]<1+d[node]){
                        d[u]=1+d[node];
                     }
                 }
             }
             int ret=-1;
             for(int i=1;i<=node;i++){
                 if(busy[i] || d[i]==-1) continue ;
                 ret=max(ret,d[i]);
             }
             cout<<ret<<endl;
          }
          for(int i=1;i<=cnt;i++) busy[c[i]]=0;
    }
    return 0;
}

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