Submission #853874

#	Time	Username	Problem	Language	Result	Execution time	Memory
853874		overwatch9	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	228 ms	6484 KiB

bitaro

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

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