Submission #930188

#	Time	Username	Problem	Language	Result	Execution time	Memory
930188		asdasdqwer	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1261 ms	377836 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], rev[UPPER];
vector<pii> pref[UPPER];
bool seen[UPPER], seen1[UPPER];
int MX[UPPER];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i=0;i<UPPER;i++) {
        MX[i] = -1;
    }

    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);
        rev[b].push_back(a);
    }

    // precalc
    for (int i=0;i<n;i++) {
        vector<int> idx = {i};
        MX[i] = 0;
        for (int x:rev[i]) {
            for (auto y:pref[x]) {
                MX[y[0]] = max(MX[y[0]], y[1]+1);
                if (!seen1[y[0]]) {
                    seen1[y[0]] = true;
                    idx.push_back(y[0]);
                }
            }
        }

        // bucket sort
        int mx = 0;
        for (auto &x:idx) {
            mx = max(mx, MX[x]);
            bucket[MX[x]].push_back(x);
        }

        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:idx) {
            bucket[MX[x]].clear();
            MX[x] = -1;
            seen1[x] = false;
        }

        pref[i] = tmp;

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

    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: 7 / 7
• Subtask 3: 86 / 86