/**
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 = 40;
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 |
7 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8408 KB |
Output is correct |
| 4 |
Correct |
9 ms |
8412 KB |
Output is correct |
| 5 |
Correct |
14 ms |
8792 KB |
Output is correct |
| 6 |
Correct |
15 ms |
8792 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8792 KB |
Output is correct |
| 8 |
Correct |
14 ms |
8900 KB |
Output is correct |
| 9 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 10 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 11 |
Correct |
16 ms |
9156 KB |
Output is correct |
| 12 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 13 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 14 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 15 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 16 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 17 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 18 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 19 |
Correct |
14 ms |
9156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8408 KB |
Output is correct |
| 4 |
Correct |
9 ms |
8412 KB |
Output is correct |
| 5 |
Correct |
14 ms |
8792 KB |
Output is correct |
| 6 |
Correct |
15 ms |
8792 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8792 KB |
Output is correct |
| 8 |
Correct |
14 ms |
8900 KB |
Output is correct |
| 9 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 10 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 11 |
Correct |
16 ms |
9156 KB |
Output is correct |
| 12 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 13 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 14 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 15 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 16 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 17 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 18 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 19 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 20 |
Correct |
654 ms |
13556 KB |
Output is correct |
| 21 |
Correct |
657 ms |
13940 KB |
Output is correct |
| 22 |
Correct |
683 ms |
13940 KB |
Output is correct |
| 23 |
Correct |
673 ms |
13940 KB |
Output is correct |
| 24 |
Correct |
814 ms |
57088 KB |
Output is correct |
| 25 |
Correct |
789 ms |
57212 KB |
Output is correct |
| 26 |
Correct |
751 ms |
57212 KB |
Output is correct |
| 27 |
Correct |
634 ms |
69196 KB |
Output is correct |
| 28 |
Correct |
637 ms |
69196 KB |
Output is correct |
| 29 |
Correct |
668 ms |
69196 KB |
Output is correct |
| 30 |
Correct |
614 ms |
69196 KB |
Output is correct |
| 31 |
Correct |
694 ms |
69196 KB |
Output is correct |
| 32 |
Correct |
663 ms |
69196 KB |
Output is correct |
| 33 |
Correct |
638 ms |
69196 KB |
Output is correct |
| 34 |
Correct |
597 ms |
69196 KB |
Output is correct |
| 35 |
Correct |
588 ms |
69196 KB |
Output is correct |
| 36 |
Correct |
724 ms |
69196 KB |
Output is correct |
| 37 |
Correct |
752 ms |
69196 KB |
Output is correct |
| 38 |
Correct |
665 ms |
69196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8408 KB |
Output is correct |
| 4 |
Correct |
9 ms |
8412 KB |
Output is correct |
| 5 |
Correct |
14 ms |
8792 KB |
Output is correct |
| 6 |
Correct |
15 ms |
8792 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8792 KB |
Output is correct |
| 8 |
Correct |
14 ms |
8900 KB |
Output is correct |
| 9 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 10 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 11 |
Correct |
16 ms |
9156 KB |
Output is correct |
| 12 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 13 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 14 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 15 |
Correct |
15 ms |
9156 KB |
Output is correct |
| 16 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 17 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 18 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 19 |
Correct |
14 ms |
9156 KB |
Output is correct |
| 20 |
Correct |
654 ms |
13556 KB |
Output is correct |
| 21 |
Correct |
657 ms |
13940 KB |
Output is correct |
| 22 |
Correct |
683 ms |
13940 KB |
Output is correct |
| 23 |
Correct |
673 ms |
13940 KB |
Output is correct |
| 24 |
Correct |
814 ms |
57088 KB |
Output is correct |
| 25 |
Correct |
789 ms |
57212 KB |
Output is correct |
| 26 |
Correct |
751 ms |
57212 KB |
Output is correct |
| 27 |
Correct |
634 ms |
69196 KB |
Output is correct |
| 28 |
Correct |
637 ms |
69196 KB |
Output is correct |
| 29 |
Correct |
668 ms |
69196 KB |
Output is correct |
| 30 |
Correct |
614 ms |
69196 KB |
Output is correct |
| 31 |
Correct |
694 ms |
69196 KB |
Output is correct |
| 32 |
Correct |
663 ms |
69196 KB |
Output is correct |
| 33 |
Correct |
638 ms |
69196 KB |
Output is correct |
| 34 |
Correct |
597 ms |
69196 KB |
Output is correct |
| 35 |
Correct |
588 ms |
69196 KB |
Output is correct |
| 36 |
Correct |
724 ms |
69196 KB |
Output is correct |
| 37 |
Correct |
752 ms |
69196 KB |
Output is correct |
| 38 |
Correct |
665 ms |
69196 KB |
Output is correct |
| 39 |
Correct |
996 ms |
69196 KB |
Output is correct |
| 40 |
Correct |
929 ms |
69196 KB |
Output is correct |
| 41 |
Execution timed out |
2051 ms |
69196 KB |
Time limit exceeded |
| 42 |
Halted |
0 ms |
0 KB |
- |
