Submission #1251650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251650		stdfloat	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1328 ms	411324 KiB

bitaro

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

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m, Q;
	cin >> n >> m >> Q;

	vector<int> E[n + 1];
	while (m--) {
		int x, y;
		cin >> x >> y;

		E[y].push_back(x);
	}

	int K = sqrt(1e5);
	vector<bool> vis(n + 1);
	vector<int> ind(n + 1);
	vector<vector<pii>> v(n + 1);
	for (int i = 1; i <= n; i++) {
		priority_queue<pii> q;
		for (auto j : E[i]) {
			q.push({v[j][0].ff, j});
		}

		while (!q.empty() && sz(v[i]) < K) {
			auto [d, x] = q.top(); q.pop();
			
			int y = v[x][ind[x]].ss;

			if (!vis[y]) {
				vis[y] = true;
				v[i].push_back({d + 1, y});
			}

			if (ind[x] + 1 < sz(v[x])) q.push({v[x][++ind[x]].ff, x});
		}

		for (auto j : E[i]) {
			ind[j] = 0;
		}
		for (auto [d, j] : v[i]) {
			vis[j] = false;
		}

		if (sz(v[i]) < K) v[i].push_back({0, i});

		int lst = INT_MAX;
		for (auto [d, j] : v[i]) {
			assert(lst >= d);
			lst = d;
		}
	}

	while (Q--) {
		int T, Y;
		cin >> T >> Y;

		vector<bool> vis(n + 1);
		while (Y--) {
			int x;
			cin >> x;

			vis[x] = true;
		}

		bool tr = false;
		for (auto [d, j] : v[T]) {
			if (!vis[j]) {
				cout << d << '\n';
				tr = true; break;
			}
		}

		if (tr) continue;

		vector<int> dp(n + 1, -1);
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) dp[i] = 0;

			for (auto j : E[i]) {
				if (~dp[j]) dp[i] = max(dp[i], dp[j] + 1);
			}
		}

		cout << dp[T] << '\n';
	}
}

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