Submission #930167

#	Time	Username	Problem	Language	Result	Execution time	Memory
930167		asdasdqwer	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	32 ms	6808 KiB

bitaro

#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;
        //         }
        //     }
        // }

        // 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;
        }
    }
}

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