#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 = len;
break;
}
}
} else {
auto dp = std::vector<int>(t + 1, -(m + 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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
720 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
600 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
720 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
600 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
29 ms |
2772 KB |
Output is correct |
21 |
Correct |
32 ms |
2896 KB |
Output is correct |
22 |
Correct |
29 ms |
2644 KB |
Output is correct |
23 |
Correct |
30 ms |
3020 KB |
Output is correct |
24 |
Correct |
555 ms |
252496 KB |
Output is correct |
25 |
Correct |
588 ms |
263900 KB |
Output is correct |
26 |
Correct |
576 ms |
263028 KB |
Output is correct |
27 |
Correct |
694 ms |
411048 KB |
Output is correct |
28 |
Correct |
657 ms |
410704 KB |
Output is correct |
29 |
Correct |
701 ms |
410768 KB |
Output is correct |
30 |
Correct |
653 ms |
410064 KB |
Output is correct |
31 |
Correct |
768 ms |
395996 KB |
Output is correct |
32 |
Correct |
673 ms |
410040 KB |
Output is correct |
33 |
Correct |
436 ms |
252600 KB |
Output is correct |
34 |
Correct |
502 ms |
206684 KB |
Output is correct |
35 |
Correct |
439 ms |
250932 KB |
Output is correct |
36 |
Correct |
553 ms |
331604 KB |
Output is correct |
37 |
Correct |
642 ms |
299692 KB |
Output is correct |
38 |
Correct |
559 ms |
332408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
720 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
600 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
29 ms |
2772 KB |
Output is correct |
21 |
Correct |
32 ms |
2896 KB |
Output is correct |
22 |
Correct |
29 ms |
2644 KB |
Output is correct |
23 |
Correct |
30 ms |
3020 KB |
Output is correct |
24 |
Correct |
555 ms |
252496 KB |
Output is correct |
25 |
Correct |
588 ms |
263900 KB |
Output is correct |
26 |
Correct |
576 ms |
263028 KB |
Output is correct |
27 |
Correct |
694 ms |
411048 KB |
Output is correct |
28 |
Correct |
657 ms |
410704 KB |
Output is correct |
29 |
Correct |
701 ms |
410768 KB |
Output is correct |
30 |
Correct |
653 ms |
410064 KB |
Output is correct |
31 |
Correct |
768 ms |
395996 KB |
Output is correct |
32 |
Correct |
673 ms |
410040 KB |
Output is correct |
33 |
Correct |
436 ms |
252600 KB |
Output is correct |
34 |
Correct |
502 ms |
206684 KB |
Output is correct |
35 |
Correct |
439 ms |
250932 KB |
Output is correct |
36 |
Correct |
553 ms |
331604 KB |
Output is correct |
37 |
Correct |
642 ms |
299692 KB |
Output is correct |
38 |
Correct |
559 ms |
332408 KB |
Output is correct |
39 |
Incorrect |
617 ms |
255668 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |