Submission #769640

#	Time	Username	Problem	Language	Result	Execution time	Memory
769640		PurpleCrayon	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	321 ms	212576 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 998244353;
const int B = 200;

int n, m, q;
vector<int> adj[N];
vector<pair<int, int>> best[N]; // sorted from biggest to smallest

void merge_into(vector<pair<int, int>>& one, vector<pair<int, int>>& two) {
    vector<pair<int, int>> ans(min(B, sz(one) + sz(two)));

    int p = 0;
    int p1 = 0, p2 = 0;
    auto move_one = [&]() {
        ans[p++] = one[p1++];
    };

    auto move_two = [&]() {
        ans[p++] = two[p2++];
    };

    while (sz(ans) < B && (p1 < sz(one) || p2 < sz(two))) {
        if (p1 == sz(one)) move_two();
        else if (p2 == sz(two)) move_one();
        else if (one[p1] > two[p2]) move_one();
        else move_two();
    }

    one.clear();
    for (auto& x : ans) one.push_back(x);
}

int dp[N];
bool bad[N];

void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[b].push_back(a);
    }

    for (int i = 0; i < n; i++) {
        for (int nxt : adj[i]) {
            merge_into(best[i], best[nxt]);
        }

        for (auto& [x, c] : best[i]) x++;
        best[i].emplace_back(0, i);
        while (sz(best[i]) > B) best[i].pop_back();
    }

    while (q--) {
        int c, k; cin >> c >> k, --c;
        if (k < B) {
            vector<int> v(k);
            for (auto& x : v) cin >> x, --x;
            for (int x : v) bad[x] = 1;

            int ans = -1;
            for (auto [x, i] : best[c]) if (!bad[i]) {
                ans = x;
                break;
            }

            for (int x : v) bad[x] = 0;

            cout << ans << '\n';
        } else {
            memset(dp, 0, sizeof(dp));
            for (int i = 0; i < k; i++) {
                int x; cin >> x, --x;
                dp[x] = -MOD;
            }

            for (int i = 0; i < n; i++) {
                for (int nxt : adj[i]) {
                    dp[i] = max(dp[i], dp[nxt] + 1);
                }
            }

            cout << (dp[c] < 0 ? -1 : dp[c]) << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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