#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pii pair<int,int>
#define fr first
#define sc second
#define pow2(i) (1<<i)
#define eb emplace_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(_i, _s, _n) for (int _i = _s; _i <= _n; ++_i)
#define FOD(_i, _s, _n) for (int _i = _s; _i >= _n; --_i)
#define firstbit(_mask) __builtin_ctz(_mask)
#define lastbit(_mask) __builtin_clz(_mask)
#define countbit(_mask) __builtin_popcount(_mask)
int getbit(int mask, int i) {
return (mask >> i) & 1;
}
void flipbit(int &mask, int i) {
mask ^= (1 << i);
}
void setbit(int &mask, int i) {
mask |= (1 << i);
}
template <typename T> inline void read(T &x) {
x = 0; char c;
while (!isdigit(c = getchar()));
do x = x*10 + c - '0';
while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x) {
if (x > 9) write(x/10);
putchar(x % 10 + 48);
}
const int dd[4]={-1, 0, 1, 0}, dc[4]={0, 1, 0, -1};
//#define PROBLEMS "bitaro"
#ifdef PROBLEMS
#define cin fi
#define cout fo
ifstream fi (PROBLEMS".inp");
ofstream fo (PROBLEMS".out");
#endif
#define camnguyenmeow ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/* /\_/\
(= ._.)
/ >? \>$
*/
bool cantgo[100005];
int mx[100005], d[100005], maxx = 100;
vector<int> a[100005];
vector<pii> dt[100005];
pii b[100005];
int main()
{
camnguyenmeow
int n, m, q, u, v, cnt;
cin >> n >> m >> q;
while (m--) {
cin >> u >> v;
a[v].push_back(u);
}
FOR(i, 1, n) {
cnt = 0;
vector<int> change;
for (int v : a[i]) {
if (!mx[v]) change.push_back(v);
mx[v] = max(mx[v], 1);
for (pii it : dt[v]) {
if (!mx[it.sc]) change.push_back(it.sc);
mx[it.sc] = max(mx[it.sc], it.fr + 1);
}
}
cnt = 0;
for (int v : change) {
b[++cnt] = {mx[v], v};
mx[v] = 0;
}
nth_element(b + 1, b + 1 + min(maxx, cnt), b + 1 + cnt, [&](const pii &A, const pii &B) {
return A.fr > B.fr;
});
dt[i].assign(min(cnt, maxx), {0, 0});
FOR(j, 0, min(cnt, maxx) - 1)
dt[i][j] = b[j + 1];
}
while (q--) {
int t, y;
cin >> t >> y;
FOR(i, 1, y) {
cin >> u; cantgo[u] = 1;
}
if (y >= maxx) {
FOR(i, 1, t) {
d[i] = 0;
for (int j : a[i])
if (!cantgo[j] || d[j])
d[i] = max(d[i], d[j] + 1);
}
if (cantgo[t] && d[t] == 0) cout << -1 <<'\n';
else cout << d[t] <<'\n';
}
else {
int ans = -1;
for (pii i : dt[t])
if (!cantgo[i.sc]) ans = max(ans, i.fr);
if (!cantgo[t]) ans = max(ans, 0);
cout << ans << '\n';
}
memset(cantgo, 0, sizeof(cantgo));
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
8 ms |
5484 KB |
Output is correct |
6 |
Correct |
5 ms |
5484 KB |
Output is correct |
7 |
Correct |
5 ms |
5484 KB |
Output is correct |
8 |
Correct |
6 ms |
5996 KB |
Output is correct |
9 |
Correct |
7 ms |
5996 KB |
Output is correct |
10 |
Correct |
7 ms |
5996 KB |
Output is correct |
11 |
Correct |
10 ms |
5868 KB |
Output is correct |
12 |
Correct |
8 ms |
5740 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
9 ms |
5612 KB |
Output is correct |
15 |
Correct |
9 ms |
5484 KB |
Output is correct |
16 |
Correct |
9 ms |
5612 KB |
Output is correct |
17 |
Correct |
6 ms |
5740 KB |
Output is correct |
18 |
Correct |
6 ms |
5612 KB |
Output is correct |
19 |
Correct |
9 ms |
5740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
8 ms |
5484 KB |
Output is correct |
6 |
Correct |
5 ms |
5484 KB |
Output is correct |
7 |
Correct |
5 ms |
5484 KB |
Output is correct |
8 |
Correct |
6 ms |
5996 KB |
Output is correct |
9 |
Correct |
7 ms |
5996 KB |
Output is correct |
10 |
Correct |
7 ms |
5996 KB |
Output is correct |
11 |
Correct |
10 ms |
5868 KB |
Output is correct |
12 |
Correct |
8 ms |
5740 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
9 ms |
5612 KB |
Output is correct |
15 |
Correct |
9 ms |
5484 KB |
Output is correct |
16 |
Correct |
9 ms |
5612 KB |
Output is correct |
17 |
Correct |
6 ms |
5740 KB |
Output is correct |
18 |
Correct |
6 ms |
5612 KB |
Output is correct |
19 |
Correct |
9 ms |
5740 KB |
Output is correct |
20 |
Correct |
107 ms |
8556 KB |
Output is correct |
21 |
Correct |
126 ms |
8556 KB |
Output is correct |
22 |
Correct |
111 ms |
8556 KB |
Output is correct |
23 |
Correct |
117 ms |
8684 KB |
Output is correct |
24 |
Correct |
403 ms |
70892 KB |
Output is correct |
25 |
Correct |
442 ms |
71948 KB |
Output is correct |
26 |
Correct |
414 ms |
71948 KB |
Output is correct |
27 |
Correct |
368 ms |
91300 KB |
Output is correct |
28 |
Correct |
370 ms |
91376 KB |
Output is correct |
29 |
Correct |
375 ms |
91372 KB |
Output is correct |
30 |
Correct |
410 ms |
91116 KB |
Output is correct |
31 |
Correct |
429 ms |
89836 KB |
Output is correct |
32 |
Correct |
385 ms |
91244 KB |
Output is correct |
33 |
Correct |
285 ms |
60524 KB |
Output is correct |
34 |
Correct |
347 ms |
55788 KB |
Output is correct |
35 |
Correct |
274 ms |
60396 KB |
Output is correct |
36 |
Correct |
348 ms |
75856 KB |
Output is correct |
37 |
Correct |
487 ms |
71788 KB |
Output is correct |
38 |
Correct |
318 ms |
75884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
8 ms |
5484 KB |
Output is correct |
6 |
Correct |
5 ms |
5484 KB |
Output is correct |
7 |
Correct |
5 ms |
5484 KB |
Output is correct |
8 |
Correct |
6 ms |
5996 KB |
Output is correct |
9 |
Correct |
7 ms |
5996 KB |
Output is correct |
10 |
Correct |
7 ms |
5996 KB |
Output is correct |
11 |
Correct |
10 ms |
5868 KB |
Output is correct |
12 |
Correct |
8 ms |
5740 KB |
Output is correct |
13 |
Correct |
6 ms |
5868 KB |
Output is correct |
14 |
Correct |
9 ms |
5612 KB |
Output is correct |
15 |
Correct |
9 ms |
5484 KB |
Output is correct |
16 |
Correct |
9 ms |
5612 KB |
Output is correct |
17 |
Correct |
6 ms |
5740 KB |
Output is correct |
18 |
Correct |
6 ms |
5612 KB |
Output is correct |
19 |
Correct |
9 ms |
5740 KB |
Output is correct |
20 |
Correct |
107 ms |
8556 KB |
Output is correct |
21 |
Correct |
126 ms |
8556 KB |
Output is correct |
22 |
Correct |
111 ms |
8556 KB |
Output is correct |
23 |
Correct |
117 ms |
8684 KB |
Output is correct |
24 |
Correct |
403 ms |
70892 KB |
Output is correct |
25 |
Correct |
442 ms |
71948 KB |
Output is correct |
26 |
Correct |
414 ms |
71948 KB |
Output is correct |
27 |
Correct |
368 ms |
91300 KB |
Output is correct |
28 |
Correct |
370 ms |
91376 KB |
Output is correct |
29 |
Correct |
375 ms |
91372 KB |
Output is correct |
30 |
Correct |
410 ms |
91116 KB |
Output is correct |
31 |
Correct |
429 ms |
89836 KB |
Output is correct |
32 |
Correct |
385 ms |
91244 KB |
Output is correct |
33 |
Correct |
285 ms |
60524 KB |
Output is correct |
34 |
Correct |
347 ms |
55788 KB |
Output is correct |
35 |
Correct |
274 ms |
60396 KB |
Output is correct |
36 |
Correct |
348 ms |
75856 KB |
Output is correct |
37 |
Correct |
487 ms |
71788 KB |
Output is correct |
38 |
Correct |
318 ms |
75884 KB |
Output is correct |
39 |
Correct |
847 ms |
72316 KB |
Output is correct |
40 |
Correct |
552 ms |
71788 KB |
Output is correct |
41 |
Correct |
1118 ms |
72300 KB |
Output is correct |
42 |
Correct |
633 ms |
72128 KB |
Output is correct |
43 |
Correct |
436 ms |
71660 KB |
Output is correct |
44 |
Correct |
514 ms |
10116 KB |
Output is correct |
45 |
Correct |
171 ms |
9068 KB |
Output is correct |
46 |
Correct |
295 ms |
8940 KB |
Output is correct |
47 |
Correct |
231 ms |
8812 KB |
Output is correct |
48 |
Correct |
122 ms |
8556 KB |
Output is correct |
49 |
Correct |
789 ms |
92508 KB |
Output is correct |
50 |
Correct |
965 ms |
91628 KB |
Output is correct |
51 |
Correct |
558 ms |
9848 KB |
Output is correct |
52 |
Correct |
335 ms |
8812 KB |
Output is correct |
53 |
Correct |
745 ms |
76396 KB |
Output is correct |
54 |
Correct |
787 ms |
72940 KB |
Output is correct |
55 |
Correct |
901 ms |
75760 KB |
Output is correct |
56 |
Correct |
1000 ms |
72428 KB |
Output is correct |
57 |
Correct |
501 ms |
9836 KB |
Output is correct |
58 |
Correct |
505 ms |
9832 KB |
Output is correct |
59 |
Correct |
359 ms |
8916 KB |
Output is correct |
60 |
Correct |
323 ms |
8812 KB |
Output is correct |
61 |
Correct |
482 ms |
91652 KB |
Output is correct |
62 |
Correct |
454 ms |
76268 KB |
Output is correct |
63 |
Correct |
506 ms |
72052 KB |
Output is correct |
64 |
Correct |
719 ms |
91828 KB |
Output is correct |
65 |
Correct |
696 ms |
76020 KB |
Output is correct |
66 |
Correct |
739 ms |
72428 KB |
Output is correct |
67 |
Correct |
1086 ms |
91628 KB |
Output is correct |
68 |
Correct |
849 ms |
76396 KB |
Output is correct |
69 |
Correct |
1053 ms |
71660 KB |
Output is correct |
70 |
Correct |
383 ms |
91724 KB |
Output is correct |
71 |
Correct |
342 ms |
76012 KB |
Output is correct |
72 |
Correct |
402 ms |
72472 KB |
Output is correct |
73 |
Correct |
413 ms |
91628 KB |
Output is correct |
74 |
Correct |
454 ms |
76140 KB |
Output is correct |
75 |
Correct |
436 ms |
72300 KB |
Output is correct |
76 |
Correct |
824 ms |
92916 KB |
Output is correct |
77 |
Correct |
893 ms |
91852 KB |
Output is correct |
78 |
Correct |
383 ms |
91752 KB |
Output is correct |
79 |
Correct |
521 ms |
9992 KB |
Output is correct |
80 |
Correct |
312 ms |
9068 KB |
Output is correct |
81 |
Correct |
158 ms |
8644 KB |
Output is correct |
82 |
Correct |
774 ms |
92652 KB |
Output is correct |
83 |
Correct |
858 ms |
90988 KB |
Output is correct |
84 |
Correct |
930 ms |
91752 KB |
Output is correct |
85 |
Correct |
947 ms |
90132 KB |
Output is correct |
86 |
Correct |
422 ms |
91628 KB |
Output is correct |
87 |
Correct |
442 ms |
90276 KB |
Output is correct |
88 |
Correct |
503 ms |
9964 KB |
Output is correct |
89 |
Correct |
495 ms |
9964 KB |
Output is correct |
90 |
Correct |
304 ms |
8940 KB |
Output is correct |
91 |
Correct |
317 ms |
8940 KB |
Output is correct |
92 |
Correct |
117 ms |
8556 KB |
Output is correct |
93 |
Correct |
116 ms |
8556 KB |
Output is correct |
94 |
Correct |
745 ms |
62188 KB |
Output is correct |
95 |
Correct |
742 ms |
57076 KB |
Output is correct |
96 |
Correct |
693 ms |
60956 KB |
Output is correct |
97 |
Correct |
881 ms |
57368 KB |
Output is correct |
98 |
Correct |
332 ms |
61096 KB |
Output is correct |
99 |
Correct |
363 ms |
56684 KB |
Output is correct |
100 |
Correct |
530 ms |
9964 KB |
Output is correct |
101 |
Correct |
519 ms |
10092 KB |
Output is correct |
102 |
Correct |
272 ms |
9196 KB |
Output is correct |
103 |
Correct |
258 ms |
9068 KB |
Output is correct |
104 |
Correct |
139 ms |
8804 KB |
Output is correct |
105 |
Correct |
119 ms |
8684 KB |
Output is correct |
106 |
Correct |
740 ms |
76980 KB |
Output is correct |
107 |
Correct |
784 ms |
73164 KB |
Output is correct |
108 |
Correct |
877 ms |
76524 KB |
Output is correct |
109 |
Correct |
1383 ms |
72428 KB |
Output is correct |
110 |
Correct |
340 ms |
76524 KB |
Output is correct |
111 |
Correct |
390 ms |
72556 KB |
Output is correct |
112 |
Correct |
540 ms |
10092 KB |
Output is correct |
113 |
Correct |
507 ms |
10044 KB |
Output is correct |
114 |
Correct |
293 ms |
8992 KB |
Output is correct |
115 |
Correct |
305 ms |
8940 KB |
Output is correct |
116 |
Correct |
117 ms |
8716 KB |
Output is correct |
117 |
Correct |
118 ms |
8556 KB |
Output is correct |
118 |
Correct |
376 ms |
91312 KB |
Output is correct |
119 |
Correct |
338 ms |
75884 KB |
Output is correct |
120 |
Correct |
625 ms |
71532 KB |
Output is correct |
121 |
Correct |
435 ms |
91244 KB |
Output is correct |
122 |
Correct |
369 ms |
75608 KB |
Output is correct |
123 |
Correct |
602 ms |
71488 KB |
Output is correct |
124 |
Correct |
366 ms |
91132 KB |
Output is correct |
125 |
Correct |
349 ms |
75884 KB |
Output is correct |
126 |
Correct |
388 ms |
71600 KB |
Output is correct |