Submission #1011626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011626		eysbutno	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	1107 ms	524288 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template<class T> bool smax(T &a, T b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool smin(T &a, T b) {
    return a > b ? a = b, 1 : 0;
}
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[--v].push_back(--u);
    }
    // this code is sketch!
    const int B = (int) sqrt(n);
    vector<vector<pii>> best(n);
    for (int i = 0; i < n; i++) {
        best[i].push_back({i, 0});
        for (int j : adj[i]) {
            for (auto [idx, len] : best[j]) {
                best[i].push_back({idx, len + 1});
            }
        }
        sort(all(best[i]), [](auto &x, auto &y) -> bool {
            return x[1] > y[1];
        });
        best[i].erase(unique(all(best[i])), end(best[i]));
        while (sz(best[i]) > B) {
            best[i].pop_back();
        }
    }
    // end
    vector<bool> ok(n, true);
    if (n > 1000) {
        return;
    }
    while (q--) {
        int t, y;
        cin >> t >> y;
        vector<int> c(y);
        for (int i = 0; i < y; i++) {
            cin >> c[i], ok[--c[i]] = false;
        }
        --t;
        int res = -1;
        if (y >= B) {
            vector<int> dp(t + 1, -1);
            dp[t] = 0;
            for (int i = t; i >= 0; i--) {
                if (dp[i] == -1) { continue; }
                if (ok[i]) { smax(res, dp[i]); }
                for (int j : adj[i]) {
                    smax(dp[j], dp[i] + 1);
                }
            }
        } else {
            for (auto [idx, len] : best[t]) {
                if (ok[idx]) { 
                    res = len;
                    break;
                }
            }
        }
        for (int i : c) { ok[i] = true; }
        cout << res << "\n";
    }
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1; // cin >> t;
    while (t--) solve();
}
/**
 * Because of the graph's structure as a DAG,
 * we can reverse the graph so that each query is finding
 * the furthest town with a beaver that can attend the party.
 * Note that because sum(y_i) is bounded, we can block out the queries.
 * If y_i >= sqrt(n), then there can be at most sqrt(n) of these queries,
 * so we can just directly compute the answer. Otherwise, we can precompute
 * the answer. Otherwise, because we have strictly < y_i "unavailable" nodes,
 * we only need to compute the sqrt(n) best paths for each node.
 */

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