Submission #1009346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009346		VMaksimoski008	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1036 ms	155632 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int maxn = 1e5 + 5;

vector<int> graph[maxn+5];
int block[maxn+5], dp[maxn+5];
vector<pair<int, int> > P[maxn+1];

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, m, Q;
    cin >> n >> m >> Q;
    const int B = 105;

    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        graph[b].push_back(a);
    }

    vector<int> ind(n+1, -1);
    for(int i=1; i<=n; i++) {
        vector<int> id;
        P[i].push_back({ 0, i });

        for(int &j : graph[i]) {
            for(auto &[d, u] : P[j]) {
                if(ind[u] == -1) id.push_back(u);
                ind[u] = max(ind[u], d + 1);
            }
        }

        for(int &u : id) P[i].push_back({ ind[u], u });
        sort(P[i].rbegin(), P[i].rend());
        while(P[i].size() > B) P[i].pop_back();
        for(int &u : id) ind[u] = -1;
    }

    while(Q--) {
        int T, Y;
        cin >> T >> Y;

        for(int i=0; i<Y; i++) {
            int x;
            cin >> x;
            block[x] = 1;
        }

        if(Y >= B) {
            dp[T] = 0;
            for(int i=1; i<=n; i++) if(i != T) dp[i] = -1e9; 

            for(int i=n; i>=1; i--)
                for(int &j : graph[i]) dp[j] = max(dp[j], dp[i] + 1);

            int mx = -1;
            for(int i=1; i<=n; i++) if(!block[i]) mx = max(mx, dp[i]);
            cout << mx << '\n';
        } else {
            bool ok = 0;
            for(auto &[d, u] : P[T]) {
                if(block[u]) continue;
                ok = 1;
                cout << d << '\n';
                break;
            }

            if(!ok) cout << -1 << '\n';
        }

        for(int i=1; i<=n; i++) block[i] = 0;
    }

    return 0;
}

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