Submission #556717

#	Time	Username	Problem	Language	Result	Execution time	Memory
556717		lunchbox	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	2074 ms	4948 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 = 300, Q = 100000;

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

void join(pair<int, int> *aa, pair<int, int> *bb, pair<int, int> *cc) {
	int i = 0, j = 0;

	for (int k = 0; k < B; k++) {
		if (i == B)
			cc[k] = bb[j++];
		else if (j == B)
			cc[k] = aa[i++];
		else if (aa[i].first > bb[j].first + 1)
			cc[k] = aa[i++];
		else
			cc[k] = bb[j++];
	}
}

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++) {
		static pair<int, int> tmp[B];

		for (int j = 0; j < B; j++)
			pp[i][j] = { -N, -1};
		pp[i][0] = {0, i};
		for (int j : gr[i]) {
			join(pp[i], pp[j], tmp);
			for (int k = 0; k < B; k++)
				pp[i][k] = tmp[k];
		}
	}
	for (int h = 1; h <= q; h++) {
		static int removed[N];
		int i, k, ans = -1;

		scanf("%d%d", &i, &k), i--;
		for (int _ = 0; _ < k; _++) {
			int j;

			scanf("%d", &j), j--;
			removed[j] = h;
		}
		if (k < B) {
			for (int _ = 0; _ < B; _++) {
				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:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d%d", &i, &j), i--, j--;
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &i, &k), i--;
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d", &j), j--;
      |    ~~~~~^~~~~~~~~~

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