Submission #1167542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167542		thinknoexit	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2095 ms	24648 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
const int SQ = sqrt(N) + 1;
vector<int> adj[N], rev[N];
set<pair<int, int>, greater<pair<int, int>>> s[N]; // (distance, index)
int dp[N], cut[N], no[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }
    for (int i = 1;i <= n;i++) {
        s[i].insert({ 0, i });
        for (auto& x : adj[i]) {
            for (auto& [d, idx] : s[x]) {
                s[i].insert({ d + 1,idx });
                if (s[i].size() > SQ) s[i].erase(--s[i].end());
            }
        }
    } // (n + m) log(sqrt(n))
    while (q--) {
        int t, y;
        cin >> t >> y;
        for (int j = 1;j <= y;j++) {
            cin >> cut[j];
            no[cut[j]] = 1;
        }
        if (y < SQ) {
            int ans = -1;
            for (auto& [d, idx] : s[t]) {
                if (no[idx]) continue;
                ans = max(ans, d);
            }
            cout << ans << '\n';
        } // sqrt(N) per operation
        else { // <= sqrt(N) times
            memset(dp, 0xc0, sizeof dp);
            for (int i = 1;i <= t;i++) {
                if (!no[i]) dp[i] = 0;
                for (auto& x : adj[i]) {
                    dp[i] = max(dp[i], dp[x] + 1);
                }
            }
            cout << max(-1, dp[t]) << '\n';
        } // m sqrt(N) for overall queries
        for (int j = 1;j <= y;j++) {
            no[cut[j]] = 0;
        }
    }
    return 0;
}

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