Submission #1279000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279000		IBory	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	590 ms	162108 KiB

bitaro

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007, LIM = 100;
vector<int> G[MAX], RG[MAX];
vector<pii> F[MAX];
int no[MAX], T[MAX], C[MAX], D[MAX];

void DFS(int cur) {
	vector<int> used;
	for (int next : G[cur]) {
		for (auto [a, b] : F[next]) {
			used.push_back(b);
			T[b] = max(T[b], a + 1);
		}
	}
	for (int n : used) {
		if (!T[n]) continue;
		F[cur].emplace_back(T[n], n);
		T[n] = 0;
	}
	F[cur].emplace_back(0, cur);
	sort(F[cur].begin(), F[cur].end(), greater<pii>());
	while (F[cur].size() > LIM) F[cur].pop_back();
}

int main() {
	int N, M, Q;
	scanf("%d %d %d", &N, &M, &Q);
	for (int i = 1; i <= M; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		G[b].push_back(a);
		RG[a].push_back(b);
	}
	
	for (int i = 1; i <= N; ++i) {
		DFS(i);
		sort(RG[i].begin(), RG[i].end());
	}

	for (int t = 0; t < Q; ++t) {
		int cur, K;
		scanf("%d %d", &cur, &K);
		vector<int> out(K);
		for (int& n : out) {
			scanf("%d", &n);
			no[n] = 1;
		}

		int ok = 0, ans = -1;
		for (auto [a, b] : F[cur]) {
			if (no[b]) continue;
			ok = 1;
			ans = a;
			break;
		}

		if (!ok && F[cur].size() == LIM) {
			memset(D, 0xf3, sizeof(D));
			for (int i = 1; i <= cur; ++i) {
				if (!no[i]) D[i] = max(D[i], 0);
				for (int next : RG[i]) {
					if (cur < next) break;
					D[next] = max(D[next], D[i] + 1);
				}
			}
			ans = max(-1, D[cur]);
		}

		printf("%d\n", ans);
		for (int n : out) no[n] = 0;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d %d", &N, &M, &Q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:33:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |                 scanf("%d %d", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |                 scanf("%d %d", &cur, &K);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:48:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |                         scanf("%d", &n);
      |                         ~~~~~^~~~~~~~~~

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