Submission #1167594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167594		thinknoexit	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2092 ms	12584 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];
vector<pair<int, int>> s[N]; // (distance, index)
map<int, int> mp;
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++) {
        vector<pair<int, int>> v, v2;
        for (auto& x : adj[i]) {
            for (auto& [d, idx] : s[x]) {
                v.push_back({ idx, -(d + 1) });
            }
        }
        v.push_back({ i, 0 });
        sort(v.begin(), v.end());
        for (auto& [idx, d] : v) {
            if (v2.empty() || v2.back().second != idx) {
                v2.push_back({ -d, idx });
                continue;
            }
        }
        sort(v2.begin(), v2.end(), greater<pair<int, int>>());
        for (int j = 0;j < min(SQ, (int)v2.size());j++) {
            s[i].push_back(v2[j]);
        }
    } // (n + m) sqrt(n) 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