#include <bits/stdc++.h>
const int32_t MAX_N = 1e5;
const int32_t BUCKET_SIZE = 50;
bool isForbidden[MAX_N + 5];
class Graph {
private:
struct Node {
int32_t id;
std::vector< std::pair< int32_t, int32_t > > dp;
std::vector< Node* > v, rev;
};
int32_t cntNodes;
Node nodes[MAX_N + 5];
public:
void Init(int32_t _cntNodes) {
cntNodes = _cntNodes;
for(int32_t i = 1; i <= cntNodes; i++) {
nodes[i].id = i;
}
}
void AddEdge(int32_t from, int32_t to) {
nodes[from].v.push_back(&nodes[to]);
nodes[to].rev.push_back(&nodes[from]);
}
void Precompute() {
for(int32_t i = 1; i <= cntNodes; i++) {
std::vector< std::pair< int32_t, int32_t > > dists;
dists.push_back({ 0, i });
for(auto &x : nodes[i].v) {
for(auto &y : x->dp) {
dists.push_back({ y.first + 1, y.second });
}
}
std::sort(dists.begin(), dists.end());
for(int32_t j = dists.size() - 1; j >= 0; j--) {
if(nodes[i].dp.size() == 0 || nodes[i].dp.back().second != dists[j].second) {
nodes[i].dp.push_back(dists[j]);
if(nodes[i].dp.size() == BUCKET_SIZE) {
break;
}
}
}
}
}
int32_t SolveSmallK(int32_t t) {
for(auto &x : nodes[t].dp) {
if(!isForbidden[x.second]) {
return x.first;
}
}
return -1;
}
int32_t SolveBigK(int32_t t) {
std::vector< int32_t > dp(t + 1, 0);
int32_t ans = (isForbidden[t] ? -1 : 0);
for(int32_t i = t - 1; i >= 1; i--) {
bool isChanged = false;
for(auto &x : nodes[i].rev) {
if(x->id <= t && (x->id == t || dp[x->id] != 0)) {
dp[i] = std::max(dp[i], dp[x->id] + 1);
isChanged = true;
}
}
if(isChanged && !isForbidden[i]) {
ans = std::max(ans, dp[i]);
}
}
return ans;
}
};
Graph g;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int32_t n, m, q;
std::cin >> n >> m >> q;
g.Init(n);
for(int32_t i = 0; i < m; i++) {
int32_t u, v;
std::cin >> u >> v;
g.AddEdge(v, u);
}
g.Precompute();
for(int32_t i = 0; i < q; i++) {
int32_t t, k;
std::cin >> t >> k;
std::vector< int32_t > c(k);
for(int32_t j = 0; j < k; j++) {
std::cin >> c[j];
isForbidden[c[j]] = true;
}
if(k >= BUCKET_SIZE) {
std::cout << g.SolveBigK(t) << '\n';
}
else {
std::cout << g.SolveSmallK(t) << '\n';
}
for(int32_t j = 0; j < k; j++) {
isForbidden[c[j]] = false;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8188 KB |
Output is correct |
2 |
Correct |
11 ms |
8188 KB |
Output is correct |
3 |
Correct |
11 ms |
8392 KB |
Output is correct |
4 |
Correct |
11 ms |
8392 KB |
Output is correct |
5 |
Correct |
18 ms |
8824 KB |
Output is correct |
6 |
Correct |
17 ms |
8844 KB |
Output is correct |
7 |
Correct |
16 ms |
8844 KB |
Output is correct |
8 |
Correct |
16 ms |
8884 KB |
Output is correct |
9 |
Correct |
17 ms |
9012 KB |
Output is correct |
10 |
Correct |
17 ms |
9012 KB |
Output is correct |
11 |
Correct |
17 ms |
9028 KB |
Output is correct |
12 |
Correct |
17 ms |
9028 KB |
Output is correct |
13 |
Correct |
18 ms |
9028 KB |
Output is correct |
14 |
Correct |
17 ms |
9028 KB |
Output is correct |
15 |
Correct |
17 ms |
9028 KB |
Output is correct |
16 |
Correct |
15 ms |
9028 KB |
Output is correct |
17 |
Correct |
18 ms |
9028 KB |
Output is correct |
18 |
Correct |
16 ms |
9028 KB |
Output is correct |
19 |
Correct |
16 ms |
9028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8188 KB |
Output is correct |
2 |
Correct |
11 ms |
8188 KB |
Output is correct |
3 |
Correct |
11 ms |
8392 KB |
Output is correct |
4 |
Correct |
11 ms |
8392 KB |
Output is correct |
5 |
Correct |
18 ms |
8824 KB |
Output is correct |
6 |
Correct |
17 ms |
8844 KB |
Output is correct |
7 |
Correct |
16 ms |
8844 KB |
Output is correct |
8 |
Correct |
16 ms |
8884 KB |
Output is correct |
9 |
Correct |
17 ms |
9012 KB |
Output is correct |
10 |
Correct |
17 ms |
9012 KB |
Output is correct |
11 |
Correct |
17 ms |
9028 KB |
Output is correct |
12 |
Correct |
17 ms |
9028 KB |
Output is correct |
13 |
Correct |
18 ms |
9028 KB |
Output is correct |
14 |
Correct |
17 ms |
9028 KB |
Output is correct |
15 |
Correct |
17 ms |
9028 KB |
Output is correct |
16 |
Correct |
15 ms |
9028 KB |
Output is correct |
17 |
Correct |
18 ms |
9028 KB |
Output is correct |
18 |
Correct |
16 ms |
9028 KB |
Output is correct |
19 |
Correct |
16 ms |
9028 KB |
Output is correct |
20 |
Correct |
844 ms |
13764 KB |
Output is correct |
21 |
Correct |
823 ms |
13832 KB |
Output is correct |
22 |
Correct |
838 ms |
13832 KB |
Output is correct |
23 |
Correct |
852 ms |
14208 KB |
Output is correct |
24 |
Correct |
975 ms |
57284 KB |
Output is correct |
25 |
Correct |
981 ms |
57284 KB |
Output is correct |
26 |
Correct |
878 ms |
57284 KB |
Output is correct |
27 |
Correct |
765 ms |
69164 KB |
Output is correct |
28 |
Correct |
809 ms |
69164 KB |
Output is correct |
29 |
Correct |
795 ms |
69248 KB |
Output is correct |
30 |
Correct |
743 ms |
69248 KB |
Output is correct |
31 |
Correct |
811 ms |
69248 KB |
Output is correct |
32 |
Correct |
797 ms |
69248 KB |
Output is correct |
33 |
Correct |
712 ms |
69248 KB |
Output is correct |
34 |
Correct |
644 ms |
69248 KB |
Output is correct |
35 |
Correct |
703 ms |
69248 KB |
Output is correct |
36 |
Correct |
775 ms |
69248 KB |
Output is correct |
37 |
Correct |
887 ms |
69248 KB |
Output is correct |
38 |
Correct |
794 ms |
69248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8188 KB |
Output is correct |
2 |
Correct |
11 ms |
8188 KB |
Output is correct |
3 |
Correct |
11 ms |
8392 KB |
Output is correct |
4 |
Correct |
11 ms |
8392 KB |
Output is correct |
5 |
Correct |
18 ms |
8824 KB |
Output is correct |
6 |
Correct |
17 ms |
8844 KB |
Output is correct |
7 |
Correct |
16 ms |
8844 KB |
Output is correct |
8 |
Correct |
16 ms |
8884 KB |
Output is correct |
9 |
Correct |
17 ms |
9012 KB |
Output is correct |
10 |
Correct |
17 ms |
9012 KB |
Output is correct |
11 |
Correct |
17 ms |
9028 KB |
Output is correct |
12 |
Correct |
17 ms |
9028 KB |
Output is correct |
13 |
Correct |
18 ms |
9028 KB |
Output is correct |
14 |
Correct |
17 ms |
9028 KB |
Output is correct |
15 |
Correct |
17 ms |
9028 KB |
Output is correct |
16 |
Correct |
15 ms |
9028 KB |
Output is correct |
17 |
Correct |
18 ms |
9028 KB |
Output is correct |
18 |
Correct |
16 ms |
9028 KB |
Output is correct |
19 |
Correct |
16 ms |
9028 KB |
Output is correct |
20 |
Correct |
844 ms |
13764 KB |
Output is correct |
21 |
Correct |
823 ms |
13832 KB |
Output is correct |
22 |
Correct |
838 ms |
13832 KB |
Output is correct |
23 |
Correct |
852 ms |
14208 KB |
Output is correct |
24 |
Correct |
975 ms |
57284 KB |
Output is correct |
25 |
Correct |
981 ms |
57284 KB |
Output is correct |
26 |
Correct |
878 ms |
57284 KB |
Output is correct |
27 |
Correct |
765 ms |
69164 KB |
Output is correct |
28 |
Correct |
809 ms |
69164 KB |
Output is correct |
29 |
Correct |
795 ms |
69248 KB |
Output is correct |
30 |
Correct |
743 ms |
69248 KB |
Output is correct |
31 |
Correct |
811 ms |
69248 KB |
Output is correct |
32 |
Correct |
797 ms |
69248 KB |
Output is correct |
33 |
Correct |
712 ms |
69248 KB |
Output is correct |
34 |
Correct |
644 ms |
69248 KB |
Output is correct |
35 |
Correct |
703 ms |
69248 KB |
Output is correct |
36 |
Correct |
775 ms |
69248 KB |
Output is correct |
37 |
Correct |
887 ms |
69248 KB |
Output is correct |
38 |
Correct |
794 ms |
69248 KB |
Output is correct |
39 |
Correct |
1102 ms |
69248 KB |
Output is correct |
40 |
Correct |
1101 ms |
69248 KB |
Output is correct |
41 |
Execution timed out |
2095 ms |
69248 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |