Submission #892156

#	Time	Username	Problem	Language	Result	Execution time	Memory
892156		box	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	463 ms	88528 KiB

bitaro

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int N = 1e5, B = 100;

int n, m, q;
vector<int> from[N];
pii dp[N][B], tmp[B];

void merge(pii *one, pii *two, pii *me) {
    static bool used[N];
    int i = 0, x = 0, y = 0;
    for (; i < B; i++) {
        while (x < B && one[x].second != -1 && used[one[x].second]) x++;
        while (y < B && two[y].second != -1 && used[two[y].second]) y++;
        if ((x == B || one[x].second == -1) && (y == B || two[y].second == -1)) break;
        if (x == B || one[x].second == -1) me[i] = {two[y].first + 1, two[y].second}, y++;
        else if (y == B || two[y].second == -1) me[i] = one[x++];
        else if (one[x].first > two[y].first + 1) me[i] = one[x++];
        else me[i] = {two[y].first + 1, two[y].second}, y++;
        used[me[i].second] = true;
    }
    for (int j = i; j < B; j++) me[j] = {-1, -1};
    for (int j = i - 1; j >= 0; j--) used[me[j].second] = false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    while (m--) {
        int l, r;
        cin >> l >> r, l--, r--;
        from[r].push_back(l);
    }
    for (int i = 0; i < n; i++) {
        fill(dp[i], dp[i] + B, pii{-1, -1});
        dp[i][0] = {0, i};
        for (int j : from[i]) merge(dp[i], dp[j], tmp), swap(dp[i], tmp);
    }
    while (q--) {
        static bool dead[N];
        int i, k;
        cin >> i >> k, i--;
        vector<int> v(k);
        for (int &i : v) cin >> i, i--, dead[i] = true;
        int ans = -1;
        if (k < B) {
            for (int h = 0; h < B; h++) {
                if (dp[i][h].second == -1) break;
                if (!dead[dp[i][h].second]) {
                    ans = dp[i][h].first;
                    break;
                }
            }
        } else {
            static int dp[N];
            fill(dp, dp + n, -1);
            dp[i] = 0;
            for (int j = i; j >= 0; j--) if (~dp[j]) {
                if (!dead[j]) ans = max(ans, dp[j]);
                for (int k : from[j]) dp[k] = max(dp[k], dp[j] + 1);
            }
        }
        cout << ans << '\n';
        for (int i : v) dead[i] = false;
    }
}

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