Submission #885053

#	Time	Username	Problem	Language	Result	Execution time	Memory
885053		MinaRagy06	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2012 ms	19320 KiB

bitaro

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

const int N = 100'005, B = 1;
vector<int> adj[N];
vector<array<int, 2>> dp[N];
int dp2[N];
bool bad[N];
void dfs(int i) {
	if (dp[i].size()) return;
	for (auto nxt : adj[i]) {
		int sz = dp[i].size();
		for (auto j : dp[nxt]) {
			dp[i].push_back(j);
		}
		inplace_merge(dp[i].begin(), dp[i].begin() + sz, dp[i].end());
		while (dp[i].size() > B) dp[i].pop_back();
	}
	for (auto &[x, idx] : dp[i]) {
		x--;
	}
	dp[i].push_back({0, i});
	inplace_merge(dp[i].begin(), dp[i].begin() + dp[i].size() - 1, dp[i].end());
}
int dfs2(int i) {
	if (~dp2[i]) return dp2[i];
	int mx = 0;
	if (bad[i]) mx = -1e9;
	for (auto nxt : adj[i]) {
		mx = max(mx, dfs2(nxt) + 1);
	}
	return dp2[i] = mx;
}
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: 0 / 86