Submission #1150482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150482		t6stks	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	827 ms	216892 KiB

bitaro

#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define F first
#define S second
#define PB push_back
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;

const int B = 150;
const int maxn = 1e5 + 5;
vector<int> from[maxn];
vector<int> adj[maxn];
bitset<maxn> blocked;
int mx[maxn];
vii best[maxn];
void sol() {
    int n, m, q;
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        from[--v].PB(--u);
        adj[u].push_back(v);
    }
    memset(mx, -1, sizeof(mx));
    for (int u = 0; u < n; u++) {
        best[u].PB({0, u});
        vector<int> used;
        for (int v: from[u]) {
            for (const pii& p: best[v]) {
                if (mx[p.S] == -1) {
                    mx[p.S] = p.F + 1;
                    used.push_back(p.S);
                } else {
                    mx[p.S] = max(mx[p.S], p.F + 1);
                }
            }
        }
        for (int x: used) {
            best[u].PB({mx[x], x});
            mx[x] = -1;
        }
        sort(ALL(best[u]), greater<>());
        while (SZ(best[u]) > B) best[u].pop_back();
    }
    while (q--) {
        int t, y;
        cin >> t >> y;
        --t;
        vector<int> yy(y);
        for (int& x: yy) {
            cin >> x;
            blocked[--x] = 1;
        }
        
        if (y >= B) {
            int ans = -1;
            vector<int> dp(n + 1, -1e9);
            dp[t] = 0;
            for (int i = t; ~i; i--) {
                for (int v: adj[i]) {
                    dp[i] = max(dp[i], dp[v] + 1);
                }
                if (!blocked[i]) ans = max(ans, dp[i]);
            }
            cout << ans << '\n';
        } else {
            bool ok = 0;
            for (auto &[dis, v]: best[t]) {
                if (!blocked[v]) {
                    cout << dis << '\n';
                    ok = 1;
                    break;
                }
            }
            if (!ok) cout << -1 << '\n';
        }
        for (int x: yy) blocked[x] = 0;
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    sol();
}

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