Submission #1212863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212863		395333em	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2067 ms	518388 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};

int32_t main(){
    iShowSpeed;
    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;
    for (int u = 1; u <= n; u++) {
        // cout << u << ": \n";
        priority_queue <pii> pq;
        for (auto v : rev[u]) {
            pq.emplace(1, v);
            // cout << v << " = " << 1 << "\n";
            for (int i = 1; i <= sq; i++) {
                auto [dis, node] = dp[v][i];
                if (dis == -1) break;
                pq.emplace(dis + 1, node);
                // cout << node << " = " << dis + 1 << "\n";
            }
        }
        id++;
        for (int i = 1; i <= sq; i++) {
            while (!pq.empty() && visited[pq.top().second] == id) pq.pop();
            if (pq.empty()) break;
            // cout << pq.top().second << " -> " << u << ": " << pq.top().first << "\n";
            dp[u][i] = pq.top();
            visited[pq.top().second] = id;
            pq.pop();
        }
        // cout << "-------------------\n";
    }
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= sq; j++) {
    //         auto [dis, node] = dp[i][j];
    //         cout << i << ": " << j << " = " << "[" << dis << ", " << node << "]\n";
    //     }
    //     cout << "-----------------------\n";
    // }
    int idx = 0;
    int cant[n + 1]; memset(cant, 0, sizeof cant);
    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 {
            int cal[n + 1]; memset(cal, -1, sizeof cal);
            cal[u] = 0;
            for (int i = u; i >= 1; i--) {
                for (auto v : adj[i]) {
                    if (cal[v] >= 0) cal[i] = max(cal[i], cal[v] + 1);
                }
                if (cant[i] != idx) ans = max(ans, cal[i]);
            }
        }
        cout << ans << "\n";
    }
}

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