Submission #930182

#TimeUsernameProblemLanguageResultExecution timeMemory
930182asdasdqwerBitaro’s Party (JOI18_bitaro)C++14
7 / 100
1107 ms524288 KiB
#include <bits/stdc++.h>
using namespace std;

#define MAXN 450
#define pii array<int,2>

bool cmp(const pii &x, const pii &y) {
    if (x[1] != y[1]) return x[1] > y[1];
    return x[0] > y[0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    vector<vector<int>> g(n);
    for (int i=0;i<m;i++) {
        int a,b;cin>>a>>b;a--;b--;
        g[a].push_back(b);
    }

    // precalc
    vector<vector<pii>> pref(n);
    for (int i=0;i<n;i++) {
        pref[i].push_back({i, 0});
    }

    vector<vector<int>> bucket(n+2);
    vector<bool> seen(n+2, false);

    for (int i=0;i<n;i++) {
        // bucket sort

        // sort(pref[i].begin(), pref[i].end(), cmp);

        int mx = 0;
        for (auto &x:pref[i]) {
            mx = max(mx, x[1]);
            bucket[x[1]].push_back(x[0]);
        }

        vector<pii> tmp;
        int cnt=0;
        for (int j=mx;j>=0;j--) {
            for (auto x:bucket[j]) {
                if (!seen[x]) {
                    seen[x] = true;
                    tmp.push_back({x, j});
                    cnt++;
                    if (cnt == MAXN) break;
                }
            }

            if (cnt == MAXN) break;
        }

        // cout<<tmp.size()<<"\n";

        for (auto &x:pref[i]) {
            bucket[x[1]].clear();
            seen[x[1]]=false;
        }

        pref[i].clear();
        pref[i] = tmp;

        // vector<pii> tmp;
        // int cnt=0;
        // for (auto x:pref[i]) {
        //     if (!seen[x[0]]) {
        //         tmp.push_back(x);
        //         seen[x[0]]=true;
        //         cnt++;
        //         if (cnt == MAXN) break;
        //     }
        // }

        // pref[i] = tmp;

        for (auto x:tmp) {
            seen[x[0]]=false;
        }

        for (int x:g[i]) {
            for (auto y:pref[i]) {
                pref[x].push_back({y[0], y[1]+1});
            }
        }
    }

    // for (int i=0;i<n;i++) {
    //     cout<<i+1<<"\n";
    //     for (auto x:pref[i]) {
    //         cout<<"node: "<<x[0]+1<<", length: "<<x[1]<<"\n";
    //     }
    //     cout<<"\n";
    // }

    for (int i=0;i<q;i++) {
        int t,y;cin>>t>>y;
        vector<int> val(y);
        for (auto &x:val){cin>>x;x--;seen[x]=true;}
        t--;
        bool found = false;

        for (auto x:pref[t]) {
            if (!seen[x[0]]) {
                cout<<x[1]<<"\n";
                found = true;
                break;
            }
        }

        if (!found && pref[t].size() >= MAXN) {
            vector<int> dp(n, 0);
            for (int i=0;i<n;i++) {
                if (seen[i]) continue;
                for (int x:g[i]) {
                    dp[x] = max(dp[x], dp[i]+1);
                }
            }

            if (dp[t] != 0 || !seen[t]) {
                cout<<dp[t]<<"\n";
            }

            else {
                cout<<"-1\n";
            }
        }

        else if (!found) {
            cout<<-1<<"\n";
        }

        for (auto x:val) {
            seen[x] = false;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...