/**
Solution:
Idea: We can precompute for each node the sqrt(n) furthest nodes with a simple dp. Then for each query
if the number of forbidden nodes is less than sqrt(n) then for sure the answer will be among the precomputed
otherwise we can simply solve it with a brutefore since the queries of this type will be less than sqrt(n).
*/
#include <bits/stdc++.h>
const int32_t MAX_N = 1e5;
const int32_t BUCKET_SIZE = 15;
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 |
10 ms |
8188 KB |
Output is correct |
2 |
Correct |
11 ms |
8188 KB |
Output is correct |
3 |
Correct |
10 ms |
8412 KB |
Output is correct |
4 |
Correct |
10 ms |
8412 KB |
Output is correct |
5 |
Correct |
13 ms |
8572 KB |
Output is correct |
6 |
Correct |
13 ms |
8572 KB |
Output is correct |
7 |
Correct |
13 ms |
8572 KB |
Output is correct |
8 |
Correct |
13 ms |
8600 KB |
Output is correct |
9 |
Correct |
13 ms |
8616 KB |
Output is correct |
10 |
Correct |
14 ms |
8620 KB |
Output is correct |
11 |
Correct |
14 ms |
8660 KB |
Output is correct |
12 |
Correct |
13 ms |
8660 KB |
Output is correct |
13 |
Correct |
13 ms |
8660 KB |
Output is correct |
14 |
Correct |
13 ms |
8660 KB |
Output is correct |
15 |
Correct |
13 ms |
8660 KB |
Output is correct |
16 |
Correct |
13 ms |
8660 KB |
Output is correct |
17 |
Correct |
13 ms |
8660 KB |
Output is correct |
18 |
Correct |
13 ms |
8660 KB |
Output is correct |
19 |
Correct |
13 ms |
8660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8188 KB |
Output is correct |
2 |
Correct |
11 ms |
8188 KB |
Output is correct |
3 |
Correct |
10 ms |
8412 KB |
Output is correct |
4 |
Correct |
10 ms |
8412 KB |
Output is correct |
5 |
Correct |
13 ms |
8572 KB |
Output is correct |
6 |
Correct |
13 ms |
8572 KB |
Output is correct |
7 |
Correct |
13 ms |
8572 KB |
Output is correct |
8 |
Correct |
13 ms |
8600 KB |
Output is correct |
9 |
Correct |
13 ms |
8616 KB |
Output is correct |
10 |
Correct |
14 ms |
8620 KB |
Output is correct |
11 |
Correct |
14 ms |
8660 KB |
Output is correct |
12 |
Correct |
13 ms |
8660 KB |
Output is correct |
13 |
Correct |
13 ms |
8660 KB |
Output is correct |
14 |
Correct |
13 ms |
8660 KB |
Output is correct |
15 |
Correct |
13 ms |
8660 KB |
Output is correct |
16 |
Correct |
13 ms |
8660 KB |
Output is correct |
17 |
Correct |
13 ms |
8660 KB |
Output is correct |
18 |
Correct |
13 ms |
8660 KB |
Output is correct |
19 |
Correct |
13 ms |
8660 KB |
Output is correct |
20 |
Correct |
284 ms |
13284 KB |
Output is correct |
21 |
Correct |
278 ms |
13440 KB |
Output is correct |
22 |
Correct |
293 ms |
13440 KB |
Output is correct |
23 |
Correct |
273 ms |
13508 KB |
Output is correct |
24 |
Correct |
403 ms |
27520 KB |
Output is correct |
25 |
Correct |
428 ms |
27520 KB |
Output is correct |
26 |
Correct |
404 ms |
27520 KB |
Output is correct |
27 |
Correct |
392 ms |
31560 KB |
Output is correct |
28 |
Correct |
415 ms |
31712 KB |
Output is correct |
29 |
Correct |
385 ms |
31712 KB |
Output is correct |
30 |
Correct |
412 ms |
31712 KB |
Output is correct |
31 |
Correct |
420 ms |
31712 KB |
Output is correct |
32 |
Correct |
399 ms |
31712 KB |
Output is correct |
33 |
Correct |
361 ms |
31712 KB |
Output is correct |
34 |
Correct |
391 ms |
31712 KB |
Output is correct |
35 |
Correct |
350 ms |
31712 KB |
Output is correct |
36 |
Correct |
439 ms |
31712 KB |
Output is correct |
37 |
Correct |
391 ms |
31712 KB |
Output is correct |
38 |
Correct |
340 ms |
31712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8188 KB |
Output is correct |
2 |
Correct |
11 ms |
8188 KB |
Output is correct |
3 |
Correct |
10 ms |
8412 KB |
Output is correct |
4 |
Correct |
10 ms |
8412 KB |
Output is correct |
5 |
Correct |
13 ms |
8572 KB |
Output is correct |
6 |
Correct |
13 ms |
8572 KB |
Output is correct |
7 |
Correct |
13 ms |
8572 KB |
Output is correct |
8 |
Correct |
13 ms |
8600 KB |
Output is correct |
9 |
Correct |
13 ms |
8616 KB |
Output is correct |
10 |
Correct |
14 ms |
8620 KB |
Output is correct |
11 |
Correct |
14 ms |
8660 KB |
Output is correct |
12 |
Correct |
13 ms |
8660 KB |
Output is correct |
13 |
Correct |
13 ms |
8660 KB |
Output is correct |
14 |
Correct |
13 ms |
8660 KB |
Output is correct |
15 |
Correct |
13 ms |
8660 KB |
Output is correct |
16 |
Correct |
13 ms |
8660 KB |
Output is correct |
17 |
Correct |
13 ms |
8660 KB |
Output is correct |
18 |
Correct |
13 ms |
8660 KB |
Output is correct |
19 |
Correct |
13 ms |
8660 KB |
Output is correct |
20 |
Correct |
284 ms |
13284 KB |
Output is correct |
21 |
Correct |
278 ms |
13440 KB |
Output is correct |
22 |
Correct |
293 ms |
13440 KB |
Output is correct |
23 |
Correct |
273 ms |
13508 KB |
Output is correct |
24 |
Correct |
403 ms |
27520 KB |
Output is correct |
25 |
Correct |
428 ms |
27520 KB |
Output is correct |
26 |
Correct |
404 ms |
27520 KB |
Output is correct |
27 |
Correct |
392 ms |
31560 KB |
Output is correct |
28 |
Correct |
415 ms |
31712 KB |
Output is correct |
29 |
Correct |
385 ms |
31712 KB |
Output is correct |
30 |
Correct |
412 ms |
31712 KB |
Output is correct |
31 |
Correct |
420 ms |
31712 KB |
Output is correct |
32 |
Correct |
399 ms |
31712 KB |
Output is correct |
33 |
Correct |
361 ms |
31712 KB |
Output is correct |
34 |
Correct |
391 ms |
31712 KB |
Output is correct |
35 |
Correct |
350 ms |
31712 KB |
Output is correct |
36 |
Correct |
439 ms |
31712 KB |
Output is correct |
37 |
Correct |
391 ms |
31712 KB |
Output is correct |
38 |
Correct |
340 ms |
31712 KB |
Output is correct |
39 |
Correct |
453 ms |
31712 KB |
Output is correct |
40 |
Execution timed out |
2044 ms |
31712 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |