Submission #1011631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011631		eysbutno	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2078 ms	410868 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!
    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
    */
    const int B = (int) sqrt(n);
    vector<int> from(n, -1);
    vector<vector<pii>> best(n);
    for (int i = 0; i < n; i++) {
		best[i].push_back({0, i});
		vector<int> from_indicies;

		for (int j : adj[i]) {
			for (auto [dist, idx] : best[j]) {
				if (from[idx] == -1) {
					// if we haven't gotten a path from this index yet
					from_indicies.push_back(idx);
					from[idx] = dist + 1;
				} else {
					// take max with already processed dist
					from[idx] = max(from[idx], dist + 1);
				}
			}
		}

		for (int j : from_indicies) { best[i].push_back({from[j], j}); }
		sort(best[i].rbegin(), best[i].rend());
		// pop until sqrt paths
		while (best[i].size() > B) { best[i].pop_back(); }

		// reset
		for (int j : from_indicies) { from[j] = -1; }
	}
    /*
    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 [dist, idx] : best[t]) {
				if (!blocked[idx]) {
					ans = dist;
					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();
}
/**
 * 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.
 */

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:66:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   66 |   while (best[i].size() > B) { best[i].pop_back(); }
      |          ~~~~~~~~~~~~~~~^~~

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