Submission #1251628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251628		stdfloat	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2094 ms	6220 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 = 0;
	// 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) < 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});
	// }

	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: 0 / 86