Submission #1349548

#TimeUsernameProblemLanguageResultExecution timeMemory
1349548Kirill22Bitaro’s Party (JOI18_bitaro)C++20
100 / 100
693 ms262332 KiB
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int K = 300;

int usd[int(1e5) + 22];
vector<pair<int, int>> merge(const vector<pair<int, int>>& a, vector<pair<int, int>> b) {
    for (auto& [x, y] : b) x++;
    vector<pair<int, int>> res;
    int i = 0, j = 0;
    while (!(i == a.size() && j == b.size())) {
        if (i == a.size()) {
            res.push_back(b[j++]);
        } else if (j == b.size()) {
            res.push_back(a[i++]);
        } else if (a[i].first > b[j].first) {
            res.push_back(a[i++]);
        } else {
            res.push_back(b[j++]);
        }
    }
    b.clear();
    for (auto& [x, y] : res) {
        if (!usd[y] && b.size() <= K) {
            usd[y] = 1;
            b.push_back({x, y});
        }
    }
    for (auto& [x, y] : b) usd[y] = 0;
    return b;
}

void solve () {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        g[y].push_back(x);
    }
    vector<vector<pair<int, int>>> dp(n);
    for (int i = 0; i < n; i++) {
        dp[i] = {{0, i}};
        for (auto& j : g[i]) {
            dp[i] = merge(dp[i], dp[j]);
        }
    }
    while (q--) {
        int v, cnt; cin >> v >> cnt; v--;
        vector<int> V(cnt); for (auto& u : V) { cin >> u; u--; }
        if (cnt <= K) {
            int ans = -1;
            for (auto& u : V) usd[u] = 1;
            for (auto& [len, u] : dp[v]) {
                if (!usd[u]) { ans = len; break; }
            }
            for (auto& u : V) usd[u] = 0;
            cout << ans << '\n';
        } else {
            for (auto& u : V) usd[u] = 1;
            vector<int> dp(n, -1);
            for (int i = 0; i < n; i++) {
                if (!usd[i]) dp[i] = 0;
                for (auto& j : g[i]) if (dp[j] >= 0) dp[i] = max(dp[i], dp[j] + 1);
            }
            cout << dp[v] << '\n';
            for (auto& u : V) usd[u] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...