Submission #1011632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011632		eysbutno	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	1140 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();
        }
    }
    /*
    vector<bool> ok(n, true);
    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]) {
            for (auto [len, idx] : best[t]) {
                if (ok[idx]) { 
                    res = len;
                    break;
                }
            }
        }
        for (int i : c) { ok[i] = true; }
        cout << res << "\n";
    }
    */
    vector<bool> blocked(n);
	for (int query = 0; query < q; query++) {
		int t, y;
		cin >> t >> y;
		t--;

		vector<int> c(y);
		for (int i = 0; i < y; i++) {
			cin >> c[i];
			blocked[--c[i]] = true;
		}

		int ans = -1;
		if (y >= B) {
			// brute force dp since number of queries is bounded by sqrt
			vector<int> dp(t + 1, -1);  // dp[i] stores longest path ending at i
			dp[t] = 0;
			for (int i = t; i >= 0; i--) {
				if (dp[i] == -1) { continue; }
				if (!blocked[i]) { ans = max(ans, dp[i]); }
				for (int j : adj[i]) { dp[j] = max(dp[j], dp[i] + 1); }
			}
		} else {
			for (auto [idx, len] : best[t]) {
				if (!blocked[idx]) {
					ans = len;
					break;
				}
			}
		}

		cout << ans << "\n";

		for (int i : c) { blocked[i] = false; }
	}
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1; // cin >> t;
    while (t--) solve();
}

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