제출 #1283112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283112		shilpoq	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2115 ms	485912 KiB

bitaro

#include<bits/stdc++.h>
//copy allowed;
#define ee <<endl;
#define vv ll l; cin>>l; vector<ll> a(l); for(ll i=0;i<l;i++)cin>>a[i]
#define tt ll t; cin>>t; while(t--)
#define pb push_back
#define fi first
#define prefs vector<ll> pref({0}); for(ll i:a)pref.pb(pref.back()+i)
#define se second
#define all(a) a.begin(),a.end()
#define ll long long
using namespace std;
int dist[100007]; 
int D=597;

int vis[100007]; 
vector<pair<int,int>> topk[100007];
const int inf = (1<<30);
            queue<pair<int, int>> q_bfs; 


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> par[n+1]; 
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        par[y].pb(x);
    }
    

    for(auto &i:topk)i.reserve(D+10); 



            vector<pair<int,int>> un;
    for(int i=1;i<=n;i++){
        topk[i] .pb( {0,i});
      for(int parent:par[i]){
             un = {};
            un.reserve(D+1);
        int jj=0;
        for(int ii=0;ii<topk[i].size();ii++){
        while(jj<topk[parent].size()&&topk[parent][jj].fi+1>=topk[i][ii].fi&&un.size()<D){
            if(!vis[topk[parent][jj].se]){
                vis[topk[parent][jj].se]=1;
                un.pb({topk[parent][jj].fi+1,topk[parent][jj].se});
        }
        jj++;}
        if(un.size()>=D)break;
            if(!vis[topk[i][ii].se]){un.pb(topk[i][ii]); vis[topk[i][ii].se] = 1;}

        }
        if(un.size()<D&&jj<topk[parent].size()){
            while(un.size()<D&&jj<topk[parent].size()){
                un.pb({topk[parent][jj].fi+1,topk[parent][jj].se});
                jj++;
            }
        }
        for(auto& p : un) {
                vis[p.se] = 0;
            }
        topk[i] = un;

      }
      


    }
    
    while(q--){
        int k;
        cin>>k;
        vv; 
        for(int i:a)vis[i]++; 
        
        if(l<D){ 
            bool g=0;
            for(pair<int,int> i:topk[k]){
                if(!vis[i.se]){ 
                    cout<<i.fi ee; g=1; break; 
                }
            }
            if(!g)cout<<-1 ee;
        }
        else{ 
            
            q_bfs.push({k, 0});
            for(int j=1; j<=n; j++) dist[j] = -1; 
            dist[k] = 0;

            
            while (!q_bfs.empty()) {
                auto [cur, d] = q_bfs.front();
                q_bfs.pop();

                
                if (d < dist[cur]) continue; 

                for (int parent : par[cur]) {
                    if (dist[parent] < dist[cur] + 1) { 
                        dist[parent] = dist[cur] + 1;
                        q_bfs.push({parent, dist[parent]});
                    }
                }
            }
            
            int mx=-1;
            for(int i=1;i<=n;i++){
                if(!vis[i]) 
                    mx = max(mx,dist[i]); 
            }
            cout << mx ee;
        }
        for(int i:a)vis[i]=0;
    }
}

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