#include <bits/stdc++.h>
using namespace std;
#ifdef evenvalue
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using ld = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
namespace Read {
int Int() {
int x;
cin >> x;
return x;
}
int64 Int64() {
int64 x;
cin >> x;
return x;
}
char Char() {
char c;
cin >> c;
return c;
}
string String() {
string s;
cin >> s;
return s;
}
double Double() {
return stod(String());
}
ld LongDouble() {
return stold(String());
}
template<typename T1, typename T2>
pair<T1, T2> Pair() {
pair<T1, T2> p;
cin >> p.first >> p.second;
return p;
}
template<typename T>
vector<T> Vec(const int n) {
vector<T> v(n);
for (T &x : v) {
cin >> x;
}
return v;
}
template<typename T>
vector<vector<T>> VecVec(const int n, const int m) {
vector<vector<T>> v(n);
for (vector<T> &vec : v) {
vec = Vec<T>(m);
}
return v;
}
}//namespace Read
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kMaxN = 2e5 + 10;
constexpr int kSqrtN = 150;
inline void solution() {
const int n = Read::Int();
const int m = Read::Int();
const int q = Read::Int();
vector<basic_string<int>> in(n);
for (int i = 0; i < m; i++) {
const int x = Read::Int() - 1;
const int y = Read::Int() - 1;
in[y].push_back(x);
}
vector<bool> busy(n);
vector<vector<pair<int, int>>> best_paths(n);
for (int x = 0; x < n; x++) {
vector<pair<int, int>> best;
if (not busy[x]) best.emplace_back(-1, x);
for (const int y : in[x]) {
best.insert(best.end(), best_paths[y].begin(), best_paths[y].end());
}
sort(best.rbegin(), best.rend());
for (const auto [dist, y] : best) {
if (busy[y]) continue;
busy[y] = true;
best_paths[x].emplace_back(dist + 1, y);
if (best_paths[x].size() == kSqrtN) break;
}
for (const auto [dist, y] : best_paths[x]) {
busy[y] = false;
}
}
vector<int> dp(n);
for (int qry = 0; qry < q; qry++) {
const int x = Read::Int() - 1;
const vector<int> nerds = Read::Vec<int>(Read::Int());
for (const int nerd : nerds) {
busy[nerd - 1] = true;
}
if (nerds.size() >= kSqrtN) {
fill(dp.begin(), dp.begin() + x + 1, 0);
for (const int nerd : nerds) {
dp[nerd - 1] = -kInf;
}
for (int y = 0; y <= x; y++) {
for (const int z : in[y]) {
dp[y] = max(dp[y], dp[z] + 1);
}
}
cout << max(dp[x], -1) << '\n';
} else {
bool found = false;
for (const auto [dist, y] : best_paths[x]) {
if (busy[y]) continue;
found = true;
cout << dist << '\n';
break;
}
if (not found) cout << -1 << '\n';
}
for (const int nerd : nerds) {
busy[nerd - 1] = false;
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
cout << fixed << setprecision(10);
int testcases = 1;
//cin >> testcases;
while (testcases--) {
solution();
}
}
# |
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 |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Correct |
13 ms |
2360 KB |
Output is correct |
9 |
Correct |
11 ms |
2392 KB |
Output is correct |
10 |
Correct |
11 ms |
2396 KB |
Output is correct |
11 |
Correct |
13 ms |
2140 KB |
Output is correct |
12 |
Correct |
7 ms |
1628 KB |
Output is correct |
13 |
Correct |
12 ms |
2140 KB |
Output is correct |
14 |
Correct |
9 ms |
1628 KB |
Output is correct |
15 |
Correct |
5 ms |
1116 KB |
Output is correct |
16 |
Correct |
9 ms |
1628 KB |
Output is correct |
17 |
Correct |
10 ms |
1884 KB |
Output is correct |
18 |
Correct |
7 ms |
1368 KB |
Output is correct |
19 |
Correct |
11 ms |
1884 KB |
Output is correct |
# |
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 |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Correct |
13 ms |
2360 KB |
Output is correct |
9 |
Correct |
11 ms |
2392 KB |
Output is correct |
10 |
Correct |
11 ms |
2396 KB |
Output is correct |
11 |
Correct |
13 ms |
2140 KB |
Output is correct |
12 |
Correct |
7 ms |
1628 KB |
Output is correct |
13 |
Correct |
12 ms |
2140 KB |
Output is correct |
14 |
Correct |
9 ms |
1628 KB |
Output is correct |
15 |
Correct |
5 ms |
1116 KB |
Output is correct |
16 |
Correct |
9 ms |
1628 KB |
Output is correct |
17 |
Correct |
10 ms |
1884 KB |
Output is correct |
18 |
Correct |
7 ms |
1368 KB |
Output is correct |
19 |
Correct |
11 ms |
1884 KB |
Output is correct |
20 |
Correct |
1577 ms |
4756 KB |
Output is correct |
21 |
Correct |
1524 ms |
4680 KB |
Output is correct |
22 |
Correct |
1544 ms |
4496 KB |
Output is correct |
23 |
Correct |
1513 ms |
6460 KB |
Output is correct |
24 |
Correct |
1070 ms |
154076 KB |
Output is correct |
25 |
Correct |
1148 ms |
159104 KB |
Output is correct |
26 |
Correct |
1149 ms |
159392 KB |
Output is correct |
27 |
Correct |
1108 ms |
217172 KB |
Output is correct |
28 |
Correct |
1084 ms |
216972 KB |
Output is correct |
29 |
Correct |
1090 ms |
217052 KB |
Output is correct |
30 |
Correct |
1267 ms |
217072 KB |
Output is correct |
31 |
Correct |
1522 ms |
211504 KB |
Output is correct |
32 |
Correct |
1270 ms |
216860 KB |
Output is correct |
33 |
Correct |
976 ms |
134736 KB |
Output is correct |
34 |
Correct |
886 ms |
115324 KB |
Output is correct |
35 |
Correct |
969 ms |
133872 KB |
Output is correct |
36 |
Correct |
1208 ms |
176668 KB |
Output is correct |
37 |
Correct |
1201 ms |
163804 KB |
Output is correct |
38 |
Correct |
1214 ms |
177324 KB |
Output is correct |
# |
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 |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
860 KB |
Output is correct |
6 |
Correct |
3 ms |
860 KB |
Output is correct |
7 |
Correct |
3 ms |
860 KB |
Output is correct |
8 |
Correct |
13 ms |
2360 KB |
Output is correct |
9 |
Correct |
11 ms |
2392 KB |
Output is correct |
10 |
Correct |
11 ms |
2396 KB |
Output is correct |
11 |
Correct |
13 ms |
2140 KB |
Output is correct |
12 |
Correct |
7 ms |
1628 KB |
Output is correct |
13 |
Correct |
12 ms |
2140 KB |
Output is correct |
14 |
Correct |
9 ms |
1628 KB |
Output is correct |
15 |
Correct |
5 ms |
1116 KB |
Output is correct |
16 |
Correct |
9 ms |
1628 KB |
Output is correct |
17 |
Correct |
10 ms |
1884 KB |
Output is correct |
18 |
Correct |
7 ms |
1368 KB |
Output is correct |
19 |
Correct |
11 ms |
1884 KB |
Output is correct |
20 |
Correct |
1577 ms |
4756 KB |
Output is correct |
21 |
Correct |
1524 ms |
4680 KB |
Output is correct |
22 |
Correct |
1544 ms |
4496 KB |
Output is correct |
23 |
Correct |
1513 ms |
6460 KB |
Output is correct |
24 |
Correct |
1070 ms |
154076 KB |
Output is correct |
25 |
Correct |
1148 ms |
159104 KB |
Output is correct |
26 |
Correct |
1149 ms |
159392 KB |
Output is correct |
27 |
Correct |
1108 ms |
217172 KB |
Output is correct |
28 |
Correct |
1084 ms |
216972 KB |
Output is correct |
29 |
Correct |
1090 ms |
217052 KB |
Output is correct |
30 |
Correct |
1267 ms |
217072 KB |
Output is correct |
31 |
Correct |
1522 ms |
211504 KB |
Output is correct |
32 |
Correct |
1270 ms |
216860 KB |
Output is correct |
33 |
Correct |
976 ms |
134736 KB |
Output is correct |
34 |
Correct |
886 ms |
115324 KB |
Output is correct |
35 |
Correct |
969 ms |
133872 KB |
Output is correct |
36 |
Correct |
1208 ms |
176668 KB |
Output is correct |
37 |
Correct |
1201 ms |
163804 KB |
Output is correct |
38 |
Correct |
1214 ms |
177324 KB |
Output is correct |
39 |
Correct |
1123 ms |
155772 KB |
Output is correct |
40 |
Correct |
1118 ms |
156904 KB |
Output is correct |
41 |
Correct |
1125 ms |
157168 KB |
Output is correct |
42 |
Correct |
1152 ms |
157120 KB |
Output is correct |
43 |
Correct |
1105 ms |
158060 KB |
Output is correct |
44 |
Correct |
1591 ms |
6528 KB |
Output is correct |
45 |
Correct |
1566 ms |
6380 KB |
Output is correct |
46 |
Correct |
1563 ms |
6752 KB |
Output is correct |
47 |
Correct |
1568 ms |
6312 KB |
Output is correct |
48 |
Correct |
1555 ms |
6416 KB |
Output is correct |
49 |
Correct |
1132 ms |
220824 KB |
Output is correct |
50 |
Correct |
1113 ms |
219476 KB |
Output is correct |
51 |
Correct |
1545 ms |
7240 KB |
Output is correct |
52 |
Correct |
1534 ms |
6424 KB |
Output is correct |
53 |
Correct |
1251 ms |
179692 KB |
Output is correct |
54 |
Correct |
1230 ms |
166944 KB |
Output is correct |
55 |
Correct |
1212 ms |
178732 KB |
Output is correct |
56 |
Correct |
1227 ms |
166948 KB |
Output is correct |
57 |
Correct |
1583 ms |
7380 KB |
Output is correct |
58 |
Correct |
1592 ms |
7272 KB |
Output is correct |
59 |
Correct |
1571 ms |
6688 KB |
Output is correct |
60 |
Correct |
1559 ms |
6712 KB |
Output is correct |
61 |
Correct |
1150 ms |
219672 KB |
Output is correct |
62 |
Correct |
1288 ms |
179428 KB |
Output is correct |
63 |
Correct |
1236 ms |
165360 KB |
Output is correct |
64 |
Correct |
1268 ms |
219500 KB |
Output is correct |
65 |
Correct |
1345 ms |
179056 KB |
Output is correct |
66 |
Correct |
1346 ms |
167264 KB |
Output is correct |
67 |
Correct |
1290 ms |
219360 KB |
Output is correct |
68 |
Correct |
1468 ms |
179396 KB |
Output is correct |
69 |
Correct |
1413 ms |
164428 KB |
Output is correct |
70 |
Correct |
1104 ms |
219644 KB |
Output is correct |
71 |
Correct |
1229 ms |
179816 KB |
Output is correct |
72 |
Correct |
1228 ms |
166064 KB |
Output is correct |
73 |
Correct |
1129 ms |
219544 KB |
Output is correct |
74 |
Correct |
1256 ms |
179432 KB |
Output is correct |
75 |
Correct |
1206 ms |
166116 KB |
Output is correct |
76 |
Correct |
1138 ms |
221260 KB |
Output is correct |
77 |
Correct |
1235 ms |
220068 KB |
Output is correct |
78 |
Correct |
1110 ms |
220168 KB |
Output is correct |
79 |
Correct |
1558 ms |
7348 KB |
Output is correct |
80 |
Correct |
1554 ms |
6376 KB |
Output is correct |
81 |
Correct |
1538 ms |
6320 KB |
Output is correct |
82 |
Correct |
1319 ms |
221116 KB |
Output is correct |
83 |
Correct |
1616 ms |
215384 KB |
Output is correct |
84 |
Correct |
1378 ms |
219540 KB |
Output is correct |
85 |
Correct |
1698 ms |
213824 KB |
Output is correct |
86 |
Correct |
1278 ms |
220188 KB |
Output is correct |
87 |
Correct |
1620 ms |
214532 KB |
Output is correct |
88 |
Correct |
1591 ms |
7596 KB |
Output is correct |
89 |
Correct |
1596 ms |
7376 KB |
Output is correct |
90 |
Correct |
1595 ms |
6568 KB |
Output is correct |
91 |
Correct |
1620 ms |
6476 KB |
Output is correct |
92 |
Correct |
1586 ms |
6548 KB |
Output is correct |
93 |
Correct |
1571 ms |
6208 KB |
Output is correct |
94 |
Correct |
1016 ms |
139032 KB |
Output is correct |
95 |
Correct |
930 ms |
118784 KB |
Output is correct |
96 |
Correct |
1101 ms |
136608 KB |
Output is correct |
97 |
Correct |
1027 ms |
119672 KB |
Output is correct |
98 |
Correct |
1016 ms |
137208 KB |
Output is correct |
99 |
Correct |
944 ms |
119308 KB |
Output is correct |
100 |
Correct |
1602 ms |
8292 KB |
Output is correct |
101 |
Correct |
1517 ms |
8684 KB |
Output is correct |
102 |
Correct |
1575 ms |
7600 KB |
Output is correct |
103 |
Correct |
1540 ms |
7672 KB |
Output is correct |
104 |
Correct |
1570 ms |
7260 KB |
Output is correct |
105 |
Correct |
1519 ms |
7208 KB |
Output is correct |
106 |
Correct |
1294 ms |
180048 KB |
Output is correct |
107 |
Correct |
1245 ms |
167308 KB |
Output is correct |
108 |
Correct |
1335 ms |
179968 KB |
Output is correct |
109 |
Correct |
1305 ms |
165796 KB |
Output is correct |
110 |
Correct |
1240 ms |
179900 KB |
Output is correct |
111 |
Correct |
1244 ms |
166752 KB |
Output is correct |
112 |
Correct |
1577 ms |
7188 KB |
Output is correct |
113 |
Correct |
1593 ms |
7432 KB |
Output is correct |
114 |
Correct |
1587 ms |
6740 KB |
Output is correct |
115 |
Correct |
1601 ms |
6960 KB |
Output is correct |
116 |
Correct |
1574 ms |
6108 KB |
Output is correct |
117 |
Correct |
1573 ms |
6848 KB |
Output is correct |
118 |
Correct |
1157 ms |
219180 KB |
Output is correct |
119 |
Correct |
1268 ms |
179996 KB |
Output is correct |
120 |
Correct |
1202 ms |
165840 KB |
Output is correct |
121 |
Correct |
1121 ms |
219472 KB |
Output is correct |
122 |
Correct |
1219 ms |
178904 KB |
Output is correct |
123 |
Correct |
1205 ms |
165560 KB |
Output is correct |
124 |
Correct |
1108 ms |
219288 KB |
Output is correct |
125 |
Correct |
1259 ms |
179872 KB |
Output is correct |
126 |
Correct |
1219 ms |
165540 KB |
Output is correct |