Submission #560426

#TimeUsernameProblemLanguageResultExecution timeMemory
560426colossal_pepeBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2052 ms13472 KiB
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int INF = 1e9;

int n, m, q, t, y;
vector<vector<int>> g;

int brutus(int u, int dp[]) {
    if (dp[u] != -1) return dp[u];
    for (int v : g[u]) {
        dp[u] = max(dp[u], brutus(v, dp) + 1);
    }
    if (dp[u] < 0) dp[u] = -INF;
    return dp[u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    g.resize(n);
    while (m--) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
    }
    int dp[n];
    bool absent[n];
    while (q--) {
        cin >> t >> y;
        t--;
        memset(dp, -1, sizeof(dp));
        dp[t] = 0;
        for (int i = 0; i <= t; i++) {
            if (dp[i] == -1) brutus(i, dp);
        }
        memset(absent, 0, sizeof(absent));
        for (int i = 0; i < y; i++) {
            int c;
            cin >> c;
            c--;
            absent[c] = 1;
        }
        int ans = -1;
        for (int i = 0; i <= t; i++) {
            if (not absent[i]) ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...