제출 #1234910

#제출 시각아이디문제언어결과실행 시간메모리
1234910hakutoBitaro’s Party (JOI18_bitaro)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

int N, M, Q;
vector<vector<int>> adj;
vector<bool> busy;
vector<int> memo;
int target;

const int NEG_INF = -1000000000;

int dfs(int u) {
    if (busy[u]) return NEG_INF;
    int &res = memo[u];
    if (res != INT_MIN) return res;
    if (u == target) return res = 0;
    int best = NEG_INF;
    for (int v : adj[u]) {
        int d = dfs(v);
        if (d > NEG_INF) best = max(best, d + 1);
    }
    return res = best;
}

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

    cin >> N >> M >> Q;
    adj.assign(N + 1, {});
    for (int i = 0; i < M; i++) {
        int S, E;
        cin >> S >> E;
        adj[S].push_back(E);
    }
    busy.resize(N + 1);
    memo.resize(N + 1);

    while (Q--) {
        cin >> target;
        int Y;
        cin >> Y;
        fill(busy.begin(), busy.end(), false);
        for (int i = 0; i < Y; i++) {
            int x;
            cin >> x;
            busy[x] = true;
        }
        for (int i = 1; i <= N; i++) memo[i] = INT_MIN;
        int ans = NEG_INF;
        for (int i = 1; i <= N; i++) {
            if (i == target || !busy[i]) {
                ans = max(ans, dfs(i));
            }
        }
        if (ans < 0) cout << -1 << '\n';
        else cout << ans << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...