Submission #556724

#	Time	Username	Problem	Language	Result	Execution time	Memory
556724		lunchbox	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	886 ms	323592 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, INF = 0x3f3f3f3f;

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

void join(pair<int, int> *aa, pair<int, int> *bb, pair<int, int> *cc) {
	static int used[N], _ = 1;

	int i = 0, j = 0;

	for (int k = 0; k < B; k++) {
		while (i < B && aa[i].second != -1 && used[aa[i].second] == _)
			i++;
		while (j < B && bb[j].second != -1 && used[bb[j].second] == _)
			j++;
		if (i == B)
			cc[k] = {bb[j].first + 1, bb[j].second}, 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].first + 1, bb[j].second}, j++;
		if (cc[k].second != -1)
			used[cc[k].second] = _;
	}
	_++;
}

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] = { -INF, -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 + 10 < B) {
			for (int _ = 0; _ < B; _++) {
				auto [d, j] = pp[i][_];

				if (j == -1)
					break;
				if (removed[j] != h)
					ans = max(ans, d);
			}
		} else {
			static int dd[N];

			memset(dd, -0x3f, n * sizeof * dd);
			dd[i] = 0;
			for (int j = i; j >= 0; j--) {
				int d = dd[j];

				if (d == -INF)
					continue;
				if (removed[j] != h)
					ans = max(ans, d);
				for (int k : gr[j])
					dd[k] = max(dd[k], d + 1);
			}
		}
		printf("%d\n", ans);
	}
}

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

Compilation message (stderr)

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

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