Submission #1123747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123747		juliany2	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	951 ms	258708 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 7, B = 317;
int n, m, q;
vector<int> adj[N];
vector<array<int, 2>> bst[N];
bool used[N];
int dp[N];

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

    cin >> n >> m >> q;

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

    for (int i = 1; i <= n; i++) {
        bst[i].push_back({0, i});
    }

    for (int i = 1; i <= n; i++) {
        for (auto &[d, x] : bst[i])
            d++;

        for (int j : adj[i]) {
            vector<array<int, 2>> c;
            auto add = [&](array<int, 2> &a) {
                if (!used[a[1]]) {
                    c.push_back(a);
                    used[a[1]] = 1;
                }
            };

            int l = 0, r = 0;
            while (c.size() < B) {
                if (l == bst[i].size() && r == bst[j].size())
                    break;

                if (r == bst[j].size() || (l < bst[i].size() && bst[i][l][0] > bst[j][r][0]))
                    add(bst[i][l++]);
                else
                    add(bst[j][r++]);

            }

            for (auto &[d, x] : c)
                used[x] = 0;
            bst[j] = c;
        }

        for (auto &[d, x] : bst[i])
            d--;
    }

    while (q--) {
        int t, k;
        cin >> t >> k;

        vector<int> ban(k);
        for (int &i : ban) {
            cin >> i;
            used[i] = 1;
        }

        if (k < B) {

            int ans = -1;
            for (auto &[d, x] : bst[t]) {
                if (!used[x]) {
                    ans = d;
                    break;
                }
            }

            cout << ans << '\n';
        }
        else {
            memset(dp, -1, sizeof(dp));
            dp[t] = 0;

            int ans = -1;
            for (int i = t; i >= 1; i--) {
                for (int j : adj[i]) {
                    if (dp[j] != -1)
                        dp[i] = max(dp[i], dp[j] + 1);
                }

                if (!used[i])
                    ans = max(ans, dp[i]);
            }

            cout << ans << '\n';
        }

        for (int i : ban)
            used[i] = 0;
    }

    return 0;
}

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