제출 #1150457

#제출 시각아이디문제언어결과실행 시간메모리
1150457t6stksBitaro’s Party (JOI18_bitaro)C++20
0 / 100
8 ms8776 KiB
#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 = 1e5 + 5;
vector<int> from[maxn];
vector<int> adj[maxn];
bitset<maxn> blocked;
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);
    }
    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;
            blocked[x] = 1;
        }
        
        if (y >= B) {
            int ans = -1;
            vector<int> dp(t + 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] && dp[i] >= 0) ans = max(ans, dp[i]);
            }
        } 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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...