#include <algorithm>
#include <array>
#include <cmath>
#include <ios>
#include <iostream>
#include <vector>
using Town = std::array<int, 2>;
auto solve() {
auto m = 0;
auto n = 0;
auto q = 0;
std::cin >> n >> m >> q;
auto adj = std::vector<std::vector<int>>(n);
for (auto i = 0; i < m; ++i) {
auto e = 0;
auto s = 0;
std::cin >> s >> e;
--s;
--e;
adj[e].push_back(s);
}
auto in_c = std::vector<bool>(n);
auto mx_lens = std::vector<int>(n);
auto lens = std::vector<std::vector<Town>>(n);
auto root = static_cast<int>(std::sqrt(n)) + 1;
while (root * root > n) {
--root;
}
for (auto i = 0; i < n; ++i) {
auto towns = std::vector<int>();
for (auto x : adj[i]) {
for (const auto& [town, len] : lens[x]) {
if (mx_lens[town] == 0) {
towns.push_back(town);
}
mx_lens[town] = std::max(mx_lens[town], len + 1);
}
}
if (static_cast<int>(std::size(towns)) >= root) {
std::nth_element(
std::begin(towns), std::begin(towns) + root - 1, std::end(towns),
[&](int town_1, int town_2) {
return mx_lens[town_1] > mx_lens[town_2];
}
);
for (auto j = 0; j < root; ++j) {
lens[i].push_back(Town({towns[j], mx_lens[towns[j]]}));
}
} else {
for (auto x : towns) {
lens[i].push_back(Town({x, mx_lens[x]}));
}
lens[i].push_back(Town({i, 0}));
}
for (auto x : towns) {
mx_lens[x] = 0;
}
}
for (auto i = 0; i < q; ++i) {
auto t = 0;
auto y = 0;
std::cin >> t >> y;
--t;
auto c = std::vector<int>(y);
for (auto& x : c) {
std::cin >> x;
--x;
in_c[x] = true;
}
auto mx_canals = -1;
if (y < root) {
for (const auto& [town, len] : lens[t]) {
if (!in_c[town]) {
mx_canals = std::max(mx_canals, len);
}
}
} else {
auto dp = std::vector<int>(t + 1, -(n + 1));
dp[t] = 0;
for (auto j = t; j >= 0; --j) {
for (auto x : adj[j]) {
dp[x] = std::max(dp[x], dp[j] + 1);
}
if (!in_c[j]) {
mx_canals = std::max(mx_canals, dp[j]);
}
}
}
std::cout << mx_canals << '\n';
for (auto x : c) {
in_c[x] = false;
}
}
}
auto main() -> int {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
856 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
856 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
34 ms |
1620 KB |
Output is correct |
21 |
Correct |
29 ms |
1624 KB |
Output is correct |
22 |
Correct |
31 ms |
1876 KB |
Output is correct |
23 |
Correct |
29 ms |
1872 KB |
Output is correct |
24 |
Correct |
570 ms |
252680 KB |
Output is correct |
25 |
Correct |
608 ms |
263944 KB |
Output is correct |
26 |
Correct |
616 ms |
262984 KB |
Output is correct |
27 |
Correct |
685 ms |
410704 KB |
Output is correct |
28 |
Correct |
722 ms |
410804 KB |
Output is correct |
29 |
Correct |
656 ms |
410808 KB |
Output is correct |
30 |
Correct |
659 ms |
410000 KB |
Output is correct |
31 |
Correct |
789 ms |
395772 KB |
Output is correct |
32 |
Correct |
640 ms |
410168 KB |
Output is correct |
33 |
Correct |
429 ms |
252584 KB |
Output is correct |
34 |
Correct |
473 ms |
206780 KB |
Output is correct |
35 |
Correct |
427 ms |
250832 KB |
Output is correct |
36 |
Correct |
559 ms |
331636 KB |
Output is correct |
37 |
Correct |
620 ms |
299804 KB |
Output is correct |
38 |
Correct |
549 ms |
332556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
856 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
2 ms |
604 KB |
Output is correct |
18 |
Correct |
2 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
34 ms |
1620 KB |
Output is correct |
21 |
Correct |
29 ms |
1624 KB |
Output is correct |
22 |
Correct |
31 ms |
1876 KB |
Output is correct |
23 |
Correct |
29 ms |
1872 KB |
Output is correct |
24 |
Correct |
570 ms |
252680 KB |
Output is correct |
25 |
Correct |
608 ms |
263944 KB |
Output is correct |
26 |
Correct |
616 ms |
262984 KB |
Output is correct |
27 |
Correct |
685 ms |
410704 KB |
Output is correct |
28 |
Correct |
722 ms |
410804 KB |
Output is correct |
29 |
Correct |
656 ms |
410808 KB |
Output is correct |
30 |
Correct |
659 ms |
410000 KB |
Output is correct |
31 |
Correct |
789 ms |
395772 KB |
Output is correct |
32 |
Correct |
640 ms |
410168 KB |
Output is correct |
33 |
Correct |
429 ms |
252584 KB |
Output is correct |
34 |
Correct |
473 ms |
206780 KB |
Output is correct |
35 |
Correct |
427 ms |
250832 KB |
Output is correct |
36 |
Correct |
559 ms |
331636 KB |
Output is correct |
37 |
Correct |
620 ms |
299804 KB |
Output is correct |
38 |
Correct |
549 ms |
332556 KB |
Output is correct |
39 |
Correct |
668 ms |
255560 KB |
Output is correct |
40 |
Correct |
575 ms |
260984 KB |
Output is correct |
41 |
Correct |
597 ms |
263664 KB |
Output is correct |
42 |
Correct |
623 ms |
261580 KB |
Output is correct |
43 |
Correct |
575 ms |
261096 KB |
Output is correct |
44 |
Correct |
59 ms |
4544 KB |
Output is correct |
45 |
Correct |
37 ms |
3664 KB |
Output is correct |
46 |
Correct |
125 ms |
3664 KB |
Output is correct |
47 |
Correct |
45 ms |
3544 KB |
Output is correct |
48 |
Correct |
39 ms |
3156 KB |
Output is correct |
49 |
Correct |
771 ms |
414120 KB |
Output is correct |
50 |
Correct |
657 ms |
413252 KB |
Output is correct |
51 |
Correct |
63 ms |
4436 KB |
Output is correct |
52 |
Correct |
122 ms |
3684 KB |
Output is correct |
53 |
Correct |
660 ms |
333392 KB |
Output is correct |
54 |
Correct |
718 ms |
303432 KB |
Output is correct |
55 |
Correct |
548 ms |
332988 KB |
Output is correct |
56 |
Correct |
636 ms |
303416 KB |
Output is correct |
57 |
Correct |
53 ms |
4436 KB |
Output is correct |
58 |
Correct |
55 ms |
4432 KB |
Output is correct |
59 |
Correct |
126 ms |
3668 KB |
Output is correct |
60 |
Correct |
134 ms |
3668 KB |
Output is correct |
61 |
Correct |
709 ms |
413452 KB |
Output is correct |
62 |
Correct |
587 ms |
334580 KB |
Output is correct |
63 |
Correct |
670 ms |
302196 KB |
Output is correct |
64 |
Correct |
775 ms |
413492 KB |
Output is correct |
65 |
Correct |
664 ms |
333376 KB |
Output is correct |
66 |
Correct |
748 ms |
303940 KB |
Output is correct |
67 |
Correct |
658 ms |
412820 KB |
Output is correct |
68 |
Correct |
587 ms |
334152 KB |
Output is correct |
69 |
Correct |
616 ms |
299544 KB |
Output is correct |
70 |
Correct |
668 ms |
413500 KB |
Output is correct |
71 |
Correct |
540 ms |
334852 KB |
Output is correct |
72 |
Correct |
627 ms |
303444 KB |
Output is correct |
73 |
Correct |
677 ms |
413420 KB |
Output is correct |
74 |
Correct |
556 ms |
334680 KB |
Output is correct |
75 |
Correct |
640 ms |
303256 KB |
Output is correct |
76 |
Correct |
763 ms |
414396 KB |
Output is correct |
77 |
Correct |
688 ms |
413264 KB |
Output is correct |
78 |
Correct |
707 ms |
413504 KB |
Output is correct |
79 |
Correct |
55 ms |
4692 KB |
Output is correct |
80 |
Correct |
111 ms |
3984 KB |
Output is correct |
81 |
Correct |
30 ms |
3164 KB |
Output is correct |
82 |
Correct |
775 ms |
414396 KB |
Output is correct |
83 |
Correct |
983 ms |
399532 KB |
Output is correct |
84 |
Correct |
664 ms |
412820 KB |
Output is correct |
85 |
Correct |
797 ms |
398160 KB |
Output is correct |
86 |
Correct |
659 ms |
412796 KB |
Output is correct |
87 |
Correct |
795 ms |
399340 KB |
Output is correct |
88 |
Correct |
54 ms |
4496 KB |
Output is correct |
89 |
Correct |
54 ms |
4660 KB |
Output is correct |
90 |
Correct |
111 ms |
3660 KB |
Output is correct |
91 |
Correct |
113 ms |
3676 KB |
Output is correct |
92 |
Correct |
32 ms |
3152 KB |
Output is correct |
93 |
Correct |
31 ms |
3420 KB |
Output is correct |
94 |
Correct |
516 ms |
256468 KB |
Output is correct |
95 |
Correct |
557 ms |
209060 KB |
Output is correct |
96 |
Correct |
461 ms |
254000 KB |
Output is correct |
97 |
Correct |
517 ms |
211972 KB |
Output is correct |
98 |
Correct |
454 ms |
255108 KB |
Output is correct |
99 |
Correct |
485 ms |
211544 KB |
Output is correct |
100 |
Correct |
55 ms |
4724 KB |
Output is correct |
101 |
Correct |
56 ms |
4692 KB |
Output is correct |
102 |
Correct |
86 ms |
3672 KB |
Output is correct |
103 |
Correct |
93 ms |
3704 KB |
Output is correct |
104 |
Correct |
34 ms |
3404 KB |
Output is correct |
105 |
Correct |
32 ms |
3404 KB |
Output is correct |
106 |
Correct |
657 ms |
334544 KB |
Output is correct |
107 |
Correct |
744 ms |
304284 KB |
Output is correct |
108 |
Correct |
552 ms |
335184 KB |
Output is correct |
109 |
Correct |
628 ms |
302372 KB |
Output is correct |
110 |
Correct |
554 ms |
335760 KB |
Output is correct |
111 |
Correct |
661 ms |
303876 KB |
Output is correct |
112 |
Correct |
58 ms |
4688 KB |
Output is correct |
113 |
Correct |
55 ms |
4560 KB |
Output is correct |
114 |
Correct |
108 ms |
3672 KB |
Output is correct |
115 |
Correct |
111 ms |
3912 KB |
Output is correct |
116 |
Correct |
30 ms |
3156 KB |
Output is correct |
117 |
Correct |
31 ms |
3304 KB |
Output is correct |
118 |
Correct |
686 ms |
412932 KB |
Output is correct |
119 |
Correct |
564 ms |
335192 KB |
Output is correct |
120 |
Correct |
635 ms |
302020 KB |
Output is correct |
121 |
Correct |
682 ms |
413020 KB |
Output is correct |
122 |
Correct |
575 ms |
333424 KB |
Output is correct |
123 |
Correct |
637 ms |
302212 KB |
Output is correct |
124 |
Correct |
660 ms |
412992 KB |
Output is correct |
125 |
Correct |
564 ms |
335072 KB |
Output is correct |
126 |
Correct |
664 ms |
301080 KB |
Output is correct |