Submission #769661

#	Time	Username	Problem	Language	Result	Execution time	Memory
769661		PurpleCrayon	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	764 ms	331664 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 = 2e5+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

bool has[N];
void merge_into(vector<pair<int, int>>& one, const vector<pair<int, int>>& two) {
    vector<pair<int, int>> ans;

    int p1 = 0, p2 = 0;
    auto move_one = [&]() {
        if (!has[one[p1].second]) {
            ans.push_back(one[p1]);
            has[one[p1].second] = 1;
        }

        p1++;
    };

    auto move_two = [&]() {
        if (!has[two[p2].second]) {
            ans.push_back(two[p2]);
            has[two[p2].second] = 1;
        }

        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 = ans;
    for (auto [_, x] : ans) has[x] = 0;
}

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 = max(ans, x);
            }

            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: 86 / 86