제출 #1297977

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

#define int long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()

#define debug(a, l, r) for (int i = (l); i <= (r); ++i) cout << (a)[i] << ' '; cout << '\n';

const int MAXN = 1e5 + 5;
const int INF = 1e18 + 7;
int n, m, q;
vector<int> radj[MAXN];

void init() {
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        radj[v].push_back(u);
    }
}

namespace subtask12{
    int dp[MAXN];
    bitset<MAXN> mark;

    bool check() {
        return (q == 1);
    }

    void solve() {
        int t, y; cin >> t >> y;
        mark.set();
        for (int i = 1; i <= y; ++i) {
            int c; cin >> c;
            mark[c] = 0;
        }

        for (int i = 1; i <= n; ++i) dp[i] = -INF;
        dp[t] = 0;
        for (int i = t; i >= 1; --i) {
            if (dp[i] == -INF) continue;
            for (int j : radj[i]) {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }

        int res = -INF;
        for (int i = 1; i <= n; ++i) 
            if (mark[i]) res = max(res, dp[i]);
        
        cout << (res == -INF ? -1 : res);
    }
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    if (subtask12::check()) return subtask12::solve(), 0;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...