Submission #1298148

#TimeUsernameProblemLanguageResultExecution timeMemory
1298148muhammad-ahmadBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2114 ms460272 KiB
#include <bits/stdc++.h>
using namespace std;

void fast_io(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
}

#define int long long
#define endl '\n'
#define ra(v) (v).rbegin(), (v).rend()

const int N = 1e5 + 5;
const int K = 300;

int n, m, q, indeg[N];
vector<int> adj[N];
pair<int,int> L[N][K];
int sz[N];
int topo[N], topo_size;

pair<int,int> tmp[2*K];

void merge_lists(int u, int v) {
    int k=0;
    for(int i=0;i<sz[u];i++) tmp[k++]={L[u][i].first+1, L[u][i].second};
    for(int i=0;i<sz[v];i++) tmp[k++]={L[v][i].first, L[v][i].second};

    sort(tmp,tmp+k,[](pair<int,int> &a,pair<int,int> &b){return a.second<b.second;});

    int idx=0;
    for(int i=0;i<k;){
        int src=tmp[i].second, best=tmp[i].first, j=i+1;
        while(j<k && tmp[j].second==src){best=max(best,tmp[j].first); j++;}
        L[v][idx++]={best, src};
        i=j;
        if(idx==K) break;
    }
    sz[v]=idx;
    sort(L[v], L[v]+sz[v], greater<pair<int,int>>());
}

void init_topo() {
    int IN[N];
    for(int i=1;i<=n;i++) IN[i]=indeg[i];
    queue<int> q;
    for(int i=1;i<=n;i++){if(IN[i]==0) q.push(i);}
    topo_size=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        topo[topo_size++]=u;
        for(int v:adj[u]){
            merge_lists(u,v);
            if(--IN[v]==0) q.push(v);
        }
    }
}

signed main(){
    fast_io();
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v; indeg[v]++; adj[u].push_back(v);
    }
    for(int i=1;i<=n;i++){L[i][0]={0,i}; sz[i]=1;}
    init_topo();

    while(q--){
        int T,Y; cin>>T>>Y;
        vector<int> C(Y);
        unordered_set<int> bad; bad.reserve(Y*2);
        for(int i=0;i<Y;i++){cin>>C[i]; bad.insert(C[i]);}

        if(Y<=K){
            bool found=0;
            for(int i=0;i<sz[T];i++){
                if(!bad.count(L[T][i].second)){cout<<L[T][i].first<<endl; found=1; break;}
            }
            if(!found) cout<<-1<<endl;
        } else {
            int ans[N];
            for(int i=1;i<=n;i++) ans[i]=0;
            for(int x:bad) ans[x]=-1e18;
            for(int i=0;i<topo_size;i++){
                int u=topo[i];
                for(int v:adj[u]) ans[v]=max(ans[v],ans[u]+1);
            }
            if(ans[T]<0) cout<<-1<<endl; else cout<<ans[T]<<endl;
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...