Submission #1298147

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

#define int long long
#define endl '\n'
const int N = 100000 + 5;
const int K = 300;

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

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() {
    int IN[N];
    for(int i = 1; i <= n; i++) IN[i] = indeg[i];
    queue<int> q;
    for(int i = 1; i <= n; i++){
        L[i][0] = {0, i};
        sz[i] = 1;
        if(IN[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: adj[u]){
            merge_lists(u,v);
            if(--IN[v]==0) q.push(v);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++){
        int u,v; cin >> u >> v;
        indeg[v]++;
        adj[u].push_back(v);
    }

    init();

    while(q--){
        int T,Y; cin>>T>>Y;
        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{
            queue<int> qq; int IN2[N], ans[N];
            for(int i=1;i<=n;i++){ IN2[i]=indeg[i]; ans[i]=0; }
            for(int x:bad) ans[x]=-1e18;
            for(int i=1;i<=n;i++) if(IN2[i]==0) qq.push(i);
            while(!qq.empty()){
                int u=qq.front(); qq.pop();
                for(int v:adj[u]){
                    ans[v]=max(ans[v],ans[u]+1);
                    if(--IN2[v]==0) qq.push(v);
                }
            }
            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...