oj.uz

Submission #1031944

# Submission time Handle Problem Language Result Execution time Memory
1031944 2024-07-23T08:55:06 Z juicy Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 992 ms 415396 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 2 ms 988 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 9 ms 3968 KB Output is correct
9 Correct 9 ms 4188 KB Output is correct
10 Correct 9 ms 4040 KB Output is correct
11 Correct 8 ms 3672 KB Output is correct
12 Correct 4 ms 1804 KB Output is correct
13 Correct 6 ms 3612 KB Output is correct
14 Correct 6 ms 2400 KB Output is correct
15 Correct 3 ms 1372 KB Output is correct
16 Correct 8 ms 2568 KB Output is correct
17 Correct 8 ms 2780 KB Output is correct
18 Correct 4 ms 1648 KB Output is correct
19 Correct 8 ms 2652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 2 ms 988 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 9 ms 3968 KB Output is correct
9 Correct 9 ms 4188 KB Output is correct
10 Correct 9 ms 4040 KB Output is correct
11 Correct 8 ms 3672 KB Output is correct
12 Correct 4 ms 1804 KB Output is correct
13 Correct 6 ms 3612 KB Output is correct
14 Correct 6 ms 2400 KB Output is correct
15 Correct 3 ms 1372 KB Output is correct
16 Correct 8 ms 2568 KB Output is correct
17 Correct 8 ms 2780 KB Output is correct
18 Correct 4 ms 1648 KB Output is correct
19 Correct 8 ms 2652 KB Output is correct
20 Correct 416 ms 6996 KB Output is correct
21 Correct 410 ms 6824 KB Output is correct
22 Correct 406 ms 6992 KB Output is correct
23 Correct 515 ms 6736 KB Output is correct
24 Correct 652 ms 258892 KB Output is correct
25 Correct 701 ms 269648 KB Output is correct
26 Correct 676 ms 269708 KB Output is correct
27 Correct 877 ms 413728 KB Output is correct
28 Correct 886 ms 413736 KB Output is correct
29 Correct 939 ms 413780 KB Output is correct
30 Correct 892 ms 412912 KB Output is correct
31 Correct 837 ms 402972 KB Output is correct
32 Correct 849 ms 412900 KB Output is correct
33 Correct 680 ms 256336 KB Output is correct
34 Correct 481 ms 211612 KB Output is correct
35 Correct 689 ms 254392 KB Output is correct
36 Correct 835 ms 334540 KB Output is correct
37 Correct 718 ms 305196 KB Output is correct
38 Correct 798 ms 335828 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 2 ms 988 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 9 ms 3968 KB Output is correct
9 Correct 9 ms 4188 KB Output is correct
10 Correct 9 ms 4040 KB Output is correct
11 Correct 8 ms 3672 KB Output is correct
12 Correct 4 ms 1804 KB Output is correct
13 Correct 6 ms 3612 KB Output is correct
14 Correct 6 ms 2400 KB Output is correct
15 Correct 3 ms 1372 KB Output is correct
16 Correct 8 ms 2568 KB Output is correct
17 Correct 8 ms 2780 KB Output is correct
18 Correct 4 ms 1648 KB Output is correct
19 Correct 8 ms 2652 KB Output is correct
20 Correct 416 ms 6996 KB Output is correct
21 Correct 410 ms 6824 KB Output is correct
22 Correct 406 ms 6992 KB Output is correct
23 Correct 515 ms 6736 KB Output is correct
24 Correct 652 ms 258892 KB Output is correct
25 Correct 701 ms 269648 KB Output is correct
26 Correct 676 ms 269708 KB Output is correct
27 Correct 877 ms 413728 KB Output is correct
28 Correct 886 ms 413736 KB Output is correct
29 Correct 939 ms 413780 KB Output is correct
30 Correct 892 ms 412912 KB Output is correct
31 Correct 837 ms 402972 KB Output is correct
32 Correct 849 ms 412900 KB Output is correct
33 Correct 680 ms 256336 KB Output is correct
34 Correct 481 ms 211612 KB Output is correct
35 Correct 689 ms 254392 KB Output is correct
36 Correct 835 ms 334540 KB Output is correct
37 Correct 718 ms 305196 KB Output is correct
38 Correct 798 ms 335828 KB Output is correct
39 Correct 674 ms 263232 KB Output is correct
40 Correct 690 ms 264272 KB Output is correct
41 Correct 713 ms 267504 KB Output is correct
42 Correct 719 ms 265296 KB Output is correct
43 Correct 651 ms 264640 KB Output is correct
44 Correct 409 ms 8276 KB Output is correct
45 Correct 484 ms 7504 KB Output is correct
46 Correct 470 ms 7388 KB Output is correct
47 Correct 431 ms 7164 KB Output is correct
48 Correct 392 ms 6992 KB Output is correct
49 Correct 916 ms 414800 KB Output is correct
50 Correct 842 ms 413472 KB Output is correct
51 Correct 428 ms 8036 KB Output is correct
52 Correct 405 ms 7256 KB Output is correct
53 Correct 834 ms 334164 KB Output is correct
54 Correct 711 ms 306396 KB Output is correct
55 Correct 792 ms 333580 KB Output is correct
56 Correct 638 ms 306380 KB Output is correct
57 Correct 407 ms 8020 KB Output is correct
58 Correct 431 ms 7928 KB Output is correct
59 Correct 389 ms 7240 KB Output is correct
60 Correct 389 ms 7260 KB Output is correct
61 Correct 940 ms 413756 KB Output is correct
62 Correct 879 ms 335084 KB Output is correct
63 Correct 702 ms 304448 KB Output is correct
64 Correct 992 ms 413548 KB Output is correct
65 Correct 970 ms 333648 KB Output is correct
66 Correct 807 ms 306772 KB Output is correct
67 Correct 799 ms 413524 KB Output is correct
68 Correct 840 ms 335128 KB Output is correct
69 Correct 595 ms 302492 KB Output is correct
70 Correct 810 ms 413904 KB Output is correct
71 Correct 764 ms 334956 KB Output is correct
72 Correct 647 ms 305804 KB Output is correct
73 Correct 829 ms 413836 KB Output is correct
74 Correct 826 ms 335076 KB Output is correct
75 Correct 631 ms 305820 KB Output is correct
76 Correct 822 ms 415396 KB Output is correct
77 Correct 745 ms 413896 KB Output is correct
78 Correct 844 ms 413976 KB Output is correct
79 Correct 381 ms 8288 KB Output is correct
80 Correct 368 ms 7248 KB Output is correct
81 Correct 375 ms 6840 KB Output is correct
82 Correct 812 ms 414288 KB Output is correct
83 Correct 792 ms 404380 KB Output is correct
84 Correct 820 ms 413068 KB Output is correct
85 Correct 882 ms 402852 KB Output is correct
86 Correct 947 ms 413012 KB Output is correct
87 Correct 819 ms 403636 KB Output is correct
88 Correct 421 ms 8268 KB Output is correct
89 Correct 414 ms 8216 KB Output is correct
90 Correct 392 ms 7328 KB Output is correct
91 Correct 412 ms 7252 KB Output is correct
92 Correct 425 ms 7060 KB Output is correct
93 Correct 404 ms 7076 KB Output is correct
94 Correct 659 ms 257444 KB Output is correct
95 Correct 555 ms 211764 KB Output is correct
96 Correct 648 ms 254960 KB Output is correct
97 Correct 479 ms 214520 KB Output is correct
98 Correct 684 ms 255948 KB Output is correct
99 Correct 514 ms 214020 KB Output is correct
100 Correct 465 ms 8216 KB Output is correct
101 Correct 523 ms 8272 KB Output is correct
102 Correct 494 ms 7136 KB Output is correct
103 Correct 445 ms 7128 KB Output is correct
104 Correct 478 ms 7004 KB Output is correct
105 Correct 492 ms 6844 KB Output is correct
106 Correct 757 ms 335100 KB Output is correct
107 Correct 637 ms 307024 KB Output is correct
108 Correct 768 ms 335956 KB Output is correct
109 Correct 619 ms 305320 KB Output is correct
110 Correct 921 ms 336208 KB Output is correct
111 Correct 698 ms 306800 KB Output is correct
112 Correct 407 ms 8180 KB Output is correct
113 Correct 372 ms 8272 KB Output is correct
114 Correct 417 ms 7356 KB Output is correct
115 Correct 407 ms 7244 KB Output is correct
116 Correct 441 ms 7060 KB Output is correct
117 Correct 424 ms 7048 KB Output is correct
118 Correct 882 ms 413472 KB Output is correct
119 Correct 869 ms 335536 KB Output is correct
120 Correct 740 ms 304932 KB Output is correct
121 Correct 902 ms 413524 KB Output is correct
122 Correct 860 ms 334160 KB Output is correct
123 Correct 724 ms 305304 KB Output is correct
124 Correct 861 ms 413560 KB Output is correct
125 Correct 797 ms 335840 KB Output is correct
126 Correct 644 ms 304248 KB Output is correct