#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 * 2));
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 |
344 KB |
Output is correct |
2 |
Correct |
1 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 |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
600 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 |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 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 |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
600 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 |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
29 ms |
1620 KB |
Output is correct |
21 |
Correct |
29 ms |
1788 KB |
Output is correct |
22 |
Correct |
29 ms |
1876 KB |
Output is correct |
23 |
Correct |
28 ms |
1872 KB |
Output is correct |
24 |
Correct |
571 ms |
252500 KB |
Output is correct |
25 |
Correct |
579 ms |
263996 KB |
Output is correct |
26 |
Correct |
606 ms |
263388 KB |
Output is correct |
27 |
Correct |
672 ms |
410748 KB |
Output is correct |
28 |
Correct |
648 ms |
410756 KB |
Output is correct |
29 |
Correct |
654 ms |
410728 KB |
Output is correct |
30 |
Correct |
635 ms |
410552 KB |
Output is correct |
31 |
Correct |
754 ms |
396108 KB |
Output is correct |
32 |
Correct |
636 ms |
410168 KB |
Output is correct |
33 |
Correct |
420 ms |
252528 KB |
Output is correct |
34 |
Correct |
466 ms |
206752 KB |
Output is correct |
35 |
Correct |
417 ms |
250784 KB |
Output is correct |
36 |
Correct |
545 ms |
331516 KB |
Output is correct |
37 |
Correct |
620 ms |
299672 KB |
Output is correct |
38 |
Correct |
533 ms |
332604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 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 |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 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 |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
600 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 |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
29 ms |
1620 KB |
Output is correct |
21 |
Correct |
29 ms |
1788 KB |
Output is correct |
22 |
Correct |
29 ms |
1876 KB |
Output is correct |
23 |
Correct |
28 ms |
1872 KB |
Output is correct |
24 |
Correct |
571 ms |
252500 KB |
Output is correct |
25 |
Correct |
579 ms |
263996 KB |
Output is correct |
26 |
Correct |
606 ms |
263388 KB |
Output is correct |
27 |
Correct |
672 ms |
410748 KB |
Output is correct |
28 |
Correct |
648 ms |
410756 KB |
Output is correct |
29 |
Correct |
654 ms |
410728 KB |
Output is correct |
30 |
Correct |
635 ms |
410552 KB |
Output is correct |
31 |
Correct |
754 ms |
396108 KB |
Output is correct |
32 |
Correct |
636 ms |
410168 KB |
Output is correct |
33 |
Correct |
420 ms |
252528 KB |
Output is correct |
34 |
Correct |
466 ms |
206752 KB |
Output is correct |
35 |
Correct |
417 ms |
250784 KB |
Output is correct |
36 |
Correct |
545 ms |
331516 KB |
Output is correct |
37 |
Correct |
620 ms |
299672 KB |
Output is correct |
38 |
Correct |
533 ms |
332604 KB |
Output is correct |
39 |
Incorrect |
601 ms |
255540 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |