제출 #1234910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234910		hakuto	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	0 ms	328 KiB

bitaro

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

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