Submission #853874

#TimeUsernameProblemLanguageResultExecution timeMemory
853874overwatch9Bitaro’s Party (JOI18_bitaro)C++17
7 / 100
228 ms6484 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 1;
const int maxm = 2000 + 1;
vector <int> adj[maxn], adjr[maxn];
bool dp[maxn][maxm];
bool ready[maxn][maxm];
bool blocked[maxn];
int max_len = -1;
bool solve(int s, int steps) {
    if (ready[s][steps])
        return dp[s][steps];
    bool ans = false;
    for (auto i : adjr[s]) {
        auto res = solve(i, steps+1);
        if (res) {
            ans = true;
            if (!blocked[i])
                max_len = max(max_len, steps+1);
        } 
    }
    if (!blocked[s]) {
        ans = true;
        max_len = max(max_len, steps);
    }
    ready[s][steps] = true;
    dp[s][steps] = ans;
    return ans;
}
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adjr[b].push_back(a);
    }
    int t, y;
    cin >> t >> y;
    for (int i = 0; i < y; i++) {
        int x;
        cin >> x;
        blocked[x] = true;
    }
    solve(t, 0);
    cout << max_len << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...