Submission #556714

#	Time	Username	Problem	Language	Result	Execution time	Memory
556714		lunchbox	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	61 ms	9024 KiB

bitaro

/*
https://oj.uz/problem/view/JOI18_bitaro
Bitaro's Party
*/
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 100000, B = 400, Q = 100000;

vector<int> gr[N];
vector<pair<int, int>> pp[N];

void run() {
	int n, m, q;

	scanf("%d%d%d", &n, &m, &q);
	while (m--) {
		int i, j;

		scanf("%d%d", &i, &j), i--, j--;
		gr[j].push_back(i);
	}
	for (int i = 0; i < n; i++) {
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

		pq.push({0, i});
		for (int j : gr[i]) {
			for (auto [d, k] : pp[j])
				pq.push({d + 1, k});
			while (pq.size() > B)
				pq.pop();
		}
		while (!pq.empty()) {
			pp[i].push_back(pq.top());
			pq.pop();
		}
	}
	for (int h = 1; h <= q; h++) {
		static int removed[N];
		int i, k, ans = -1;

		scanf("%d%d", &i, &k), i--;
		while (k--) {
			int j;

			scanf("%d", &j), j--;
			removed[j] = h;
		}
		if (k < B) {
			for (auto [d, j] : pp[i])
				if (removed[j] != h)
					ans = max(ans, d);
		} else {
			static int dd[N];
			priority_queue<pair<int, int>> pq;

			memset(dd, -1, n * sizeof * dd);
			pq.push({dd[i] = 0, i});
			while (!pq.empty()) {
				auto [d, i] = pq.top();

				if (dd[i] != d)
					continue;
				if (removed[i] != h)
					ans = max(ans, d);
				for (int j : gr[i])
					if (d + 1 > dd[j])
						pq.push({dd[j] = d + 1, j});
			}
		}
		printf("%d\n", ans);
	}

}

int main() {
	run();
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void run()':
bitaro.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d%d", &i, &j), i--, j--;
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &i, &k), i--;
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |    scanf("%d", &j), j--;
      |    ~~~~~^~~~~~~~~~

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