Submission #1167658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167658		thinknoexit	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1383 ms	413700 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)
int ch[N];
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].push_back({ i, 0 });
        for (auto& x : adj[i]) { // merge
            vector<pair<int, int>> v;
            int pl = 0, pr = 0;
            while (pl < (int)s[i].size() && pr < (int)s[x].size()) {
                if (s[i][pl].second < s[x][pr].second + 1) {
                    v.push_back({ s[x][pr].first, s[x][pr++].second + 1 });
                }
                else {
                    v.push_back({ s[i][pl].first, s[i][pl++].second });
                }
            }
            while (pl < (int)s[i].size()) {
                v.push_back({ s[i][pl].first, s[i][pl++].second });
            }
            while (pr < (int)s[x].size()) {
                v.push_back({ s[x][pr].first, s[x][pr++].second + 1 });
            }
            s[i].clear();
            for (int j = 0;j < (int)v.size() && (int)s[i].size() < SQ;j++) {
                if (!ch[v[j].first]) s[i].push_back(v[j]), ch[v[j].first] = 1;
            }
            for (int j = 0;j < (int)v.size();j++) {
                ch[v[j].first] = 0;
            }
        }
        // for (auto& x : s[i]) {
        //     cout << x.first << ' ' << x.second << '\n';
        // }
        // cout << '\n';
    } // (n + m) 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& [idx, d] : 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: 7 / 7
• Subtask 3: 86 / 86