Submission #930183

#	Time	Username	Problem	Language	Result	Execution time	Memory
930183		asdasdqwer	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1000 ms	524288 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

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

int val[UPPER], dp[UPPER];
vector<int> g[UPPER], bucket[UPPER];
vector<pii> pref[UPPER];
bool seen[UPPER];


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

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


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

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

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

        pref[i].clear();
        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<q;i++) {
        int t,y;cin>>t>>y;
        for (int i=0;i<y;i++){cin>>val[i];val[i]--;seen[val[i]]=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) {
            for (int i=0;i<n;i++) {
                dp[i] = 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 (int i=0;i<y;i++) {
            seen[val[i]] = false;
        }
    }
}

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