Submission #1240530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240530		duckindog	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2094 ms	13244 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m, q;
vector<int> ad[N], rAd[N];
int deg[N];

bool mk[N];

int f[N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

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

    vector<int> order;
    { // toposort
        for (int u = 1; u <= n; ++u) { 
            for (const auto& v : ad[u]) deg[v] += 1;
        }
        queue<int> q;
        for (int i = 1; i <= n; ++i) if (!deg[i]) q.push(i);
        while (q.size()) { 
            auto u = q.front(); q.pop();
            order.push_back(u);
            for (const auto& v : ad[u]) { 
                if (!--deg[v]) q.push(v);
            }
        }
    }

    reverse(order.begin(), order.end());
    while (q--) { 
        int x, k; cin >> x >> k;

        vector<int> vt(k);
        for (auto& u : vt) cin >> u, mk[u] = true;

        int answer = -1;

        fill(f + 1, f + n + 1, -1'000'000);
        f[x] = 0;
        for (const auto& u : order) { 
            for (const auto& v : rAd[u]) f[v] = max(f[v], f[u] + 1);
            if (!mk[u]) answer = max(answer, f[u]);
        }

        cout << answer << "\n";

        for (const auto& u : vt) mk[u] = false;
    }
}

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