Submission #885086

#	Time	Username	Problem	Language	Result	Execution time	Memory
885086		MinaRagy06	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	949 ms	118608 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 100'005, B = 100;
vector<int> adj[N];
vector<array<int, 2>> dp[N];
int dp2[N], mx[N];
bool bad[N], vis[N];
void dfs(int i) {
	if (dp[i].size()) return;
	vector<int> todo;
	for (auto nxt : adj[i]) {
		dfs(nxt);
		for (auto j : dp[nxt]) {
 			if (!vis[j[1]]) {
				todo.push_back(j[1]);
				vis[j[1]] = 1;
				mx[j[1]] = j[0];
 			} else {
				mx[j[1]] = max(mx[j[1]], j[0]);
			}
		}
	}
	dp[i].push_back({0, i});
	for (auto j : todo) {
		vis[j] = 0;
		bool resort = 0;
		if (dp[i].size() < B) {
			dp[i].push_back({mx[j] + 1, j});
			resort = 1;
		} else if (mx[j] + 1 >= dp[i].back()[0]) {
			dp[i].back() = {mx[j] + 1, j};
			resort = 1;
		}
		if (resort) {
			for (int j = dp[i].size() - 1; j >= 1; j--) {
				if (dp[i][j][0] >= dp[i][j - 1][0]) {
					swap(dp[i][j], dp[i][j - 1]);
				} else {
					break;
				}
			}
		}
	}
}
int dfs2(int i) {
	if (~dp2[i]) return dp2[i];
	int best = 0;
	if (bad[i]) best = -1e9;
	for (auto nxt : adj[i]) {
		best = max(best, dfs2(nxt) + 1);
	}
	return dp2[i] = best;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		dfs(i);
	}
	while (q--) {
		int t, y;
		cin >> t >> y;
		int c[y];
		for (int i = 0; i < y; i++) {
			cin >> c[i];
			bad[c[i]] = 1;
		}
		if (y >= B) {
			for (int i = 1; i <= n; i++) {
				dp2[i] = -1;
			}
			cout << max(-1, dfs2(t)) << '\n';
		} else {
			int ans = -1;
			for (auto [x, i] : dp[t]) {
				if (bad[i]) continue;
				ans = x;
				break;
			}
			cout << ans << '\n';
		}
		for (int i = 0; i < y; i++) {
			bad[c[i]] = 0;
		}
	}
	return 0;
}

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