#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
using pp=pair<int, int>;
const int maxn = int(1e5) + 10;
const int B = 300;
int n, m, q;
vector<int> re[maxn];
vector<pp> prec[maxn];
int seen[maxn];
int nt;
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i=1; i<=m; ++i) {
int s, e; cin >> s >> e;
re[e].push_back(s);
}
for (int i=1; i<=n; ++i) {
prec[i].reserve(B);
prec[i].push_back({0, i});
for (int j:re[i]) {
vector<pp> tmp, &v1 = prec[i], &v2 = prec[j];
int i1 = 0, i2 = 0;
int s1 = int(v1.size()), s2 = int(v2.size());
++nt;
while (int(tmp.size()) < B && (i1 < s1 || i2 < s2)) {
if (i1 < s1 && (i2 == s2 || v1[i1].first >= v2[i2].first+1)) {
if (seen[v1[i1].second] != nt) {
tmp.push_back(v1[i1]);
}
++i1;
} else {
if (seen[v2[i2].second] != nt) {
tmp.push_back(v2[i2]);
++tmp.back().first;
}
++i2;
}
seen[tmp.back().second] = nt;
}
swap(v1, tmp);
}
}
for (;q--;) {
int dest, igs; cin >> dest >> igs;
static int ign[maxn];
++nt;
for (int i=0; i<igs; ++i) {
cin >> ign[i];
seen[ign[i]] = nt;
}
if (igs < B) {
bool found = 0;
for (auto [dist, from]:prec[dest]) {
if (seen[from] != nt) {
cout << dist << '\n';
found = 1;
break;
}
}
if (!found) {
cout << "-1\n";
}
continue;
}
static int qd[maxn];
fill(qd+1, qd+dest+1, -1);
int ans = -1;
qd[dest] = 0;
for (int i=dest; 1<=i; --i) if (qd[i] != -1) {
if (seen[i] != nt) {
ans = max(ans, qd[i]);
}
for (int j:re[i]) {
qd[j] = max(qd[j], qd[i]+1);
}
}
cout << ans << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5020 KB |
Output is correct |
5 |
Correct |
6 ms |
5792 KB |
Output is correct |
6 |
Correct |
6 ms |
5708 KB |
Output is correct |
7 |
Correct |
6 ms |
5708 KB |
Output is correct |
8 |
Correct |
14 ms |
8360 KB |
Output is correct |
9 |
Correct |
13 ms |
8396 KB |
Output is correct |
10 |
Correct |
13 ms |
8396 KB |
Output is correct |
11 |
Correct |
13 ms |
7972 KB |
Output is correct |
12 |
Correct |
8 ms |
6348 KB |
Output is correct |
13 |
Correct |
13 ms |
7828 KB |
Output is correct |
14 |
Correct |
12 ms |
7428 KB |
Output is correct |
15 |
Correct |
9 ms |
6476 KB |
Output is correct |
16 |
Correct |
11 ms |
7280 KB |
Output is correct |
17 |
Correct |
12 ms |
7524 KB |
Output is correct |
18 |
Correct |
8 ms |
6492 KB |
Output is correct |
19 |
Correct |
11 ms |
7600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5020 KB |
Output is correct |
5 |
Correct |
6 ms |
5792 KB |
Output is correct |
6 |
Correct |
6 ms |
5708 KB |
Output is correct |
7 |
Correct |
6 ms |
5708 KB |
Output is correct |
8 |
Correct |
14 ms |
8360 KB |
Output is correct |
9 |
Correct |
13 ms |
8396 KB |
Output is correct |
10 |
Correct |
13 ms |
8396 KB |
Output is correct |
11 |
Correct |
13 ms |
7972 KB |
Output is correct |
12 |
Correct |
8 ms |
6348 KB |
Output is correct |
13 |
Correct |
13 ms |
7828 KB |
Output is correct |
14 |
Correct |
12 ms |
7428 KB |
Output is correct |
15 |
Correct |
9 ms |
6476 KB |
Output is correct |
16 |
Correct |
11 ms |
7280 KB |
Output is correct |
17 |
Correct |
12 ms |
7524 KB |
Output is correct |
18 |
Correct |
8 ms |
6492 KB |
Output is correct |
19 |
Correct |
11 ms |
7600 KB |
Output is correct |
20 |
Correct |
870 ms |
9532 KB |
Output is correct |
21 |
Correct |
795 ms |
9528 KB |
Output is correct |
22 |
Correct |
867 ms |
9464 KB |
Output is correct |
23 |
Correct |
880 ms |
9540 KB |
Output is correct |
24 |
Correct |
869 ms |
284036 KB |
Output is correct |
25 |
Correct |
903 ms |
295716 KB |
Output is correct |
26 |
Correct |
931 ms |
294820 KB |
Output is correct |
27 |
Correct |
1098 ms |
410600 KB |
Output is correct |
28 |
Correct |
1130 ms |
410680 KB |
Output is correct |
29 |
Correct |
1096 ms |
410568 KB |
Output is correct |
30 |
Correct |
1128 ms |
410084 KB |
Output is correct |
31 |
Correct |
1096 ms |
395972 KB |
Output is correct |
32 |
Correct |
1109 ms |
409904 KB |
Output is correct |
33 |
Correct |
863 ms |
295244 KB |
Output is correct |
34 |
Correct |
780 ms |
250128 KB |
Output is correct |
35 |
Correct |
854 ms |
293332 KB |
Output is correct |
36 |
Correct |
938 ms |
363640 KB |
Output is correct |
37 |
Correct |
891 ms |
332848 KB |
Output is correct |
38 |
Correct |
936 ms |
364452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
5020 KB |
Output is correct |
5 |
Correct |
6 ms |
5792 KB |
Output is correct |
6 |
Correct |
6 ms |
5708 KB |
Output is correct |
7 |
Correct |
6 ms |
5708 KB |
Output is correct |
8 |
Correct |
14 ms |
8360 KB |
Output is correct |
9 |
Correct |
13 ms |
8396 KB |
Output is correct |
10 |
Correct |
13 ms |
8396 KB |
Output is correct |
11 |
Correct |
13 ms |
7972 KB |
Output is correct |
12 |
Correct |
8 ms |
6348 KB |
Output is correct |
13 |
Correct |
13 ms |
7828 KB |
Output is correct |
14 |
Correct |
12 ms |
7428 KB |
Output is correct |
15 |
Correct |
9 ms |
6476 KB |
Output is correct |
16 |
Correct |
11 ms |
7280 KB |
Output is correct |
17 |
Correct |
12 ms |
7524 KB |
Output is correct |
18 |
Correct |
8 ms |
6492 KB |
Output is correct |
19 |
Correct |
11 ms |
7600 KB |
Output is correct |
20 |
Correct |
870 ms |
9532 KB |
Output is correct |
21 |
Correct |
795 ms |
9528 KB |
Output is correct |
22 |
Correct |
867 ms |
9464 KB |
Output is correct |
23 |
Correct |
880 ms |
9540 KB |
Output is correct |
24 |
Correct |
869 ms |
284036 KB |
Output is correct |
25 |
Correct |
903 ms |
295716 KB |
Output is correct |
26 |
Correct |
931 ms |
294820 KB |
Output is correct |
27 |
Correct |
1098 ms |
410600 KB |
Output is correct |
28 |
Correct |
1130 ms |
410680 KB |
Output is correct |
29 |
Correct |
1096 ms |
410568 KB |
Output is correct |
30 |
Correct |
1128 ms |
410084 KB |
Output is correct |
31 |
Correct |
1096 ms |
395972 KB |
Output is correct |
32 |
Correct |
1109 ms |
409904 KB |
Output is correct |
33 |
Correct |
863 ms |
295244 KB |
Output is correct |
34 |
Correct |
780 ms |
250128 KB |
Output is correct |
35 |
Correct |
854 ms |
293332 KB |
Output is correct |
36 |
Correct |
938 ms |
363640 KB |
Output is correct |
37 |
Correct |
891 ms |
332848 KB |
Output is correct |
38 |
Correct |
936 ms |
364452 KB |
Output is correct |
39 |
Correct |
982 ms |
287436 KB |
Output is correct |
40 |
Correct |
931 ms |
289628 KB |
Output is correct |
41 |
Correct |
919 ms |
292684 KB |
Output is correct |
42 |
Correct |
904 ms |
290436 KB |
Output is correct |
43 |
Correct |
892 ms |
290128 KB |
Output is correct |
44 |
Correct |
903 ms |
9924 KB |
Output is correct |
45 |
Correct |
867 ms |
9692 KB |
Output is correct |
46 |
Correct |
860 ms |
9536 KB |
Output is correct |
47 |
Correct |
892 ms |
9432 KB |
Output is correct |
48 |
Correct |
857 ms |
9464 KB |
Output is correct |
49 |
Correct |
1177 ms |
410392 KB |
Output is correct |
50 |
Correct |
1108 ms |
409976 KB |
Output is correct |
51 |
Correct |
816 ms |
9796 KB |
Output is correct |
52 |
Correct |
783 ms |
9500 KB |
Output is correct |
53 |
Correct |
978 ms |
362676 KB |
Output is correct |
54 |
Correct |
941 ms |
332812 KB |
Output is correct |
55 |
Correct |
923 ms |
362904 KB |
Output is correct |
56 |
Correct |
907 ms |
333248 KB |
Output is correct |
57 |
Correct |
884 ms |
9876 KB |
Output is correct |
58 |
Correct |
924 ms |
9852 KB |
Output is correct |
59 |
Correct |
869 ms |
9492 KB |
Output is correct |
60 |
Correct |
877 ms |
9608 KB |
Output is correct |
61 |
Correct |
1214 ms |
410308 KB |
Output is correct |
62 |
Correct |
1000 ms |
363920 KB |
Output is correct |
63 |
Correct |
914 ms |
332356 KB |
Output is correct |
64 |
Correct |
1420 ms |
410332 KB |
Output is correct |
65 |
Correct |
1096 ms |
363332 KB |
Output is correct |
66 |
Correct |
990 ms |
334428 KB |
Output is correct |
67 |
Correct |
1107 ms |
410324 KB |
Output is correct |
68 |
Correct |
1024 ms |
364004 KB |
Output is correct |
69 |
Correct |
886 ms |
330668 KB |
Output is correct |
70 |
Correct |
1142 ms |
410692 KB |
Output is correct |
71 |
Correct |
1016 ms |
364344 KB |
Output is correct |
72 |
Correct |
920 ms |
334048 KB |
Output is correct |
73 |
Correct |
1140 ms |
410816 KB |
Output is correct |
74 |
Correct |
975 ms |
364316 KB |
Output is correct |
75 |
Correct |
917 ms |
333972 KB |
Output is correct |
76 |
Correct |
1173 ms |
411308 KB |
Output is correct |
77 |
Correct |
1118 ms |
410772 KB |
Output is correct |
78 |
Correct |
1121 ms |
411148 KB |
Output is correct |
79 |
Correct |
829 ms |
10184 KB |
Output is correct |
80 |
Correct |
805 ms |
9916 KB |
Output is correct |
81 |
Correct |
784 ms |
9968 KB |
Output is correct |
82 |
Correct |
1150 ms |
410692 KB |
Output is correct |
83 |
Correct |
1175 ms |
396548 KB |
Output is correct |
84 |
Correct |
1103 ms |
410244 KB |
Output is correct |
85 |
Correct |
1099 ms |
395504 KB |
Output is correct |
86 |
Correct |
1123 ms |
410420 KB |
Output is correct |
87 |
Correct |
1117 ms |
396612 KB |
Output is correct |
88 |
Correct |
891 ms |
10260 KB |
Output is correct |
89 |
Correct |
906 ms |
10052 KB |
Output is correct |
90 |
Correct |
860 ms |
9784 KB |
Output is correct |
91 |
Correct |
902 ms |
9724 KB |
Output is correct |
92 |
Correct |
860 ms |
9804 KB |
Output is correct |
93 |
Correct |
874 ms |
9796 KB |
Output is correct |
94 |
Correct |
903 ms |
294936 KB |
Output is correct |
95 |
Correct |
788 ms |
249156 KB |
Output is correct |
96 |
Correct |
862 ms |
293020 KB |
Output is correct |
97 |
Correct |
760 ms |
252956 KB |
Output is correct |
98 |
Correct |
869 ms |
294724 KB |
Output is correct |
99 |
Correct |
752 ms |
252408 KB |
Output is correct |
100 |
Correct |
924 ms |
10160 KB |
Output is correct |
101 |
Correct |
889 ms |
10172 KB |
Output is correct |
102 |
Correct |
881 ms |
9708 KB |
Output is correct |
103 |
Correct |
886 ms |
9772 KB |
Output is correct |
104 |
Correct |
878 ms |
9732 KB |
Output is correct |
105 |
Correct |
864 ms |
9924 KB |
Output is correct |
106 |
Correct |
983 ms |
363184 KB |
Output is correct |
107 |
Correct |
944 ms |
333228 KB |
Output is correct |
108 |
Correct |
991 ms |
364660 KB |
Output is correct |
109 |
Correct |
950 ms |
332856 KB |
Output is correct |
110 |
Correct |
1020 ms |
364832 KB |
Output is correct |
111 |
Correct |
928 ms |
334572 KB |
Output is correct |
112 |
Correct |
880 ms |
10100 KB |
Output is correct |
113 |
Correct |
931 ms |
10164 KB |
Output is correct |
114 |
Correct |
853 ms |
9996 KB |
Output is correct |
115 |
Correct |
876 ms |
9756 KB |
Output is correct |
116 |
Correct |
874 ms |
9968 KB |
Output is correct |
117 |
Correct |
882 ms |
9796 KB |
Output is correct |
118 |
Correct |
1099 ms |
410200 KB |
Output is correct |
119 |
Correct |
1006 ms |
364348 KB |
Output is correct |
120 |
Correct |
889 ms |
333216 KB |
Output is correct |
121 |
Correct |
1117 ms |
410200 KB |
Output is correct |
122 |
Correct |
929 ms |
363496 KB |
Output is correct |
123 |
Correct |
888 ms |
332996 KB |
Output is correct |
124 |
Correct |
1109 ms |
410200 KB |
Output is correct |
125 |
Correct |
936 ms |
364228 KB |
Output is correct |
126 |
Correct |
887 ms |
331672 KB |
Output is correct |