Submission #1031944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031944		juicy	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	992 ms	415396 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	const int S = 320, inf = 1e9;

	int N, M, Q; cin >> N >> M >> Q;
	vector<vector<int>> g(N);
	while (M--) {
		int u, v; cin >> u >> v; --u, --v;
		g[u].push_back(v);
	}
	vector<vector<array<int, 2>>> cands(N);
	vector<bool> vs(N);
	auto mrg = [&](vector<array<int, 2>> A, vector<array<int, 2>> B) {
		vector<array<int, 2>> res;
		auto add = [&](const array<int, 2> &elem) {
			if (!vs[elem[1]]) {
				res.push_back(elem);
				vs[elem[1]] = 1;
			}
		};
		for (auto &x : A) {
			++x[0];
		}
		for (int i = 0, j = 0; res.size() < S && (i < A.size() || j < B.size()); ) {
			if (i == A.size()) {
				add(B[j++]);
			} else if (j == B.size()) {
				add(A[i++]);
			} else if (A[i][0] > B[j][0]) {
				add(A[i++]);
			} else {
				add(B[j++]);
			}
		} 
		for (auto &x : res) {
			vs[x[1]] = 0;
		}
		return res;
	};
	for (int i = 0; i < N; ++i) {
		cands[i] = mrg({{-1, i}}, cands[i]);
		for (int j : g[i]) {
			cands[j] = mrg(cands[i], cands[j]);
		}
	}
	vector<int> dp(N);
	while (Q--) {
		int T, Y; cin >> T >> Y; --T;
		vector<int> C(Y);
		for (int &x : C) {
			cin >> x; --x;
			vs[x] = 1;
		}
		if (Y >= S) {
			fill(dp.begin(), dp.end(), -inf);
			for (int i = 0; i < N; ++i) {
				if (!vs[i]) {
					dp[i] = max(dp[i], 0);
				}
				for (int j : g[i]) {
					dp[j] = max(dp[j], dp[i] + 1);
				}
			}
			cout << (dp[T] >= 0 ? dp[T] : -1) << "\n";
		} else {
			int res = -1;
			for (auto &x : cands[T]) {
				if (!vs[x[1]]) {
					res = x[0];
					break;
				}
			}
			cout << res << "\n";
		}
		for (int &x : C) {
			vs[x] = 0;
		}
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In lambda function:
bitaro.cpp:35:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 0, j = 0; res.size() < S && (i < A.size() || j < B.size()); ) {
      |                                             ~~^~~~~~~~~~
bitaro.cpp:35:63: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 0, j = 0; res.size() < S && (i < A.size() || j < B.size()); ) {
      |                                                             ~~^~~~~~~~~~
bitaro.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    if (i == A.size()) {
      |        ~~^~~~~~~~~~~
bitaro.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    } else if (j == B.size()) {
      |               ~~^~~~~~~~~~~

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