Submission #1213233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213233		395333em	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1203 ms	522280 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>

using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e18;

signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n, m, q; cin >> n >> m >> q; int sq = sqrt(n); sq++;
    vector <int> adj[n + 1], rev[n + 1];
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].emb(v);
        rev[v].emb(u);
    }
    pii dp[n + 5][sq + 5];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= sq; j++) dp[i][j] = {-1, -1};
    int visited[n + 1]; memset(visited, 0, sizeof visited);
    int id = 0;
    int stidx[n + 1]; memset(stidx, 0, sizeof stidx);
    for (int u = 1; u <= n; u++) {
        priority_queue <tuple <int, int, int, int>> pq;
        for (auto v : rev[u]) {
            pq.emplace(1, -v, 0, v);
            if (dp[v][1].first != -1) pq.emplace(dp[v][1].first + 1, -dp[v][1].second, 1, v);
        }
        id++;
        for (int i = 1; i <= sq; i++) {
            while (!pq.empty() && visited[-get <1> (pq.top())] == id) {
                int root = get <3> (pq.top());
                int nowidx = get <2> (pq.top());
                pq.pop();
                if (nowidx == 0) continue;
                if (nowidx != sq && dp[root][nowidx + 1].first != -1) pq.emplace(dp[root][nowidx + 1].first + 1, -dp[root][nowidx + 1].second, nowidx + 1, root);
            }
            if (pq.empty()) break;
            dp[u][i] = {get <0> (pq.top()), -get <1> (pq.top())};
            visited[-get <1> (pq.top())] = id;
            int root = get <3> (pq.top());
            int nowidx = get <2> (pq.top());
            pq.pop();
            if (nowidx == 0) continue;
            if (nowidx != sq && dp[root][nowidx + 1].first != -1) pq.emplace(dp[root][nowidx + 1].first + 1, -dp[root][nowidx + 1].second, nowidx + 1, root);
        }
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": " << "\n";
    //     for (int j = 1; j <= sq; j++) {
    //         if (dp[i][j].first == -1) break;
    //         cout << i << ", " << j << " = " << dp[i][j].first << ", " << dp[i][j].second << "\n";
    //     }
    //     cout << "--------------\n";
    // }
    int idx = 0;
    int cant[n + 1]; memset(cant, 0, sizeof cant);
    int cal[n + 1], cali[n + 1]; 
    memset(cal, -1, sizeof cal);
    memset(cali, -1, sizeof cali);
    while (q--) {
        idx++;
        int u, cnt; cin >> u >> cnt;
        for (int i = 1; i <= cnt; i++) {
            int x; cin >> x;
            cant[x] = idx;
        }
        int ans = (cant[u] == idx ? -1 : 0);
        if (cnt < sq) {
            for (int i = 1; i <= sq; i++) {
                auto [dis, node] = dp[u][i];
                if (node == -1) break;
                // cout << dis << ", " << node << "\n";
                if (cant[node] == idx) continue;
                ans = dis;
                break;
            }
        }
        else {
            cal[u] = 0;
            cali[u] = idx;
            for (int i = u; i >= 1; i--) {
                if (i != u) {
                    cal[i] = -1;
                    for (auto v : adj[i]) {
                        if (cali[v] == idx) cal[i] = max(cal[i], cal[v] + 1);
                    }
                    if (cal[i] != -1) cali[i] = idx;
                }
                if (cant[i] != idx) ans = max(ans, cal[i]);
            }
        }
        cout << ans << "\n";
    }
}

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