제출 #1150453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150453		t6stks	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	829 ms	240236 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 = 100;
const int maxn = 2e5 + 5;
vector<int> from[maxn];
bitset<maxn> blocked;
void sol() {
    int n, m, q;
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        from[--v].PB(--u);
    }
    vector<vii> best(n);
    for (int u = 0; u < n; u++) {
        best[u].PB({0, u});
        for (int v: from[u]) {
            for (const pii& p: best[v]) {
                best[u].PB({p.F + 1, p.S});
            }
        }
        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;
            --x;
        }
        
        if (y >= B) {
            vector<int> dp(t + 1);
            for (int x: yy) {
                if (x <= t)
                    dp[x] = -1;
            }
            for (int i = 0; i <= t; i++) {
                for (int v: from[i]) {
                    if (dp[v] == -1) continue;
                    dp[i] = max(dp[i], dp[v] + 1);
                }
            }
            cout << dp[t] << '\n';
        } else {
            for (int x: yy) blocked[x] = 1;
            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: 0 / 86