제출 #999456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999456		envifly	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	784 ms	146068 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
const int SQ = 100;  // cutoff for sqrt decomp

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<int>> rg(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		rg[--v].push_back(--u);
	}

	// stores the 100 longest paths ending at i
	vector<vector<pair<int, int>>> path_sizes(n);
	vector<int> from(n, -1);  // longest path starting at that node

	for (int i = 0; i < n; i++) {
		path_sizes[i].push_back({0, i});
		vector<int> from_indicies;

		for (int j : rg[i]) {
			for (auto [dist, idx] : path_sizes[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) { path_sizes[i].push_back({from[j], j}); }
		sort(path_sizes[i].rbegin(), path_sizes[i].rend());
		// pop until sqrt paths
		while (path_sizes[i].size() > SQ) { path_sizes[i].pop_back(); }

		// reset
		for (int j : from_indicies) { from[j] = -1; }
	}

	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 >= SQ) {
			// 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 : rg[i]) { dp[j] = max(dp[j], dp[i] + 1); }
			}
		} else {
			for (auto [dist, idx] : path_sizes[t]) {
				if (!blocked[idx]) {
					ans = dist;
					break;
				}
			}
		}

		cout << ans << "\n";

		for (int i : c) { blocked[i] = false; }
	}
}

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