/**
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 = 316;
bool isInVector[MAX_N + 5];
bool isForbidden[MAX_N + 5];
std::vector< std::pair< int32_t, int32_t > > Merge(const std::vector< std::pair< int32_t, int32_t> > &v1,
const std::vector< std::pair< int32_t, int32_t > > &v2) {
std::vector< std::pair< int32_t, int32_t > > ans;
int32_t ind1 = 0, ind2 = 0;
while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
if(ind1 < v1.size()) {
if(ind2 < v2.size()) {
if(v1[ind1].first >= v2[ind2].first) {
if(!isInVector[v1[ind1].second]) {
isInVector[v1[ind1].second] = true;
ans.push_back(v1[ind1]);
}
ind1++;
}
else {
if(!isInVector[v2[ind2].second]) {
isInVector[v2[ind2].second] = true;
ans.push_back(v2[ind2]);
}
ind2++;
}
}
else {
if(!isInVector[v1[ind1].second]) {
isInVector[v1[ind1].second] = true;
ans.push_back(v1[ind1]);
}
ind1++;
}
}
else {
if(!isInVector[v2[ind2].second]) {
isInVector[v2[ind2].second] = true;
ans.push_back(v2[ind2]);
}
ind2++;
}
}
for(auto &x : ans) {
isInVector[x.second] = false;
}
return ans;
}
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;
nodes[i].dp.push_back({ 0, i });
for(auto &x : nodes[i].v) {
auto aux = x->dp;
for(auto &y : aux) {
y.first++;
}
nodes[i].dp = Merge(nodes[i].dp, aux);
}
}
}
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;
}
}
}
Compilation message
bitaro.cpp: In function 'std::vector<std::pair<int, int> > Merge(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
~~~~~^~~~~~~~~~~
bitaro.cpp:20:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
~~~~~^~~~~~~~~~~
bitaro.cpp:21:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind1 < v1.size()) {
~~~~~^~~~~~~~~~~
bitaro.cpp:22:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind2 < v2.size()) {
~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8308 KB |
Output is correct |
3 |
Correct |
9 ms |
8308 KB |
Output is correct |
4 |
Correct |
9 ms |
8464 KB |
Output is correct |
5 |
Correct |
13 ms |
8852 KB |
Output is correct |
6 |
Correct |
14 ms |
8868 KB |
Output is correct |
7 |
Correct |
13 ms |
8868 KB |
Output is correct |
8 |
Correct |
22 ms |
11812 KB |
Output is correct |
9 |
Correct |
22 ms |
11940 KB |
Output is correct |
10 |
Correct |
22 ms |
11940 KB |
Output is correct |
11 |
Correct |
22 ms |
11940 KB |
Output is correct |
12 |
Correct |
16 ms |
11940 KB |
Output is correct |
13 |
Correct |
21 ms |
11940 KB |
Output is correct |
14 |
Correct |
19 ms |
11940 KB |
Output is correct |
15 |
Correct |
16 ms |
11940 KB |
Output is correct |
16 |
Correct |
19 ms |
11940 KB |
Output is correct |
17 |
Correct |
20 ms |
11940 KB |
Output is correct |
18 |
Correct |
17 ms |
11940 KB |
Output is correct |
19 |
Correct |
20 ms |
11940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8308 KB |
Output is correct |
3 |
Correct |
9 ms |
8308 KB |
Output is correct |
4 |
Correct |
9 ms |
8464 KB |
Output is correct |
5 |
Correct |
13 ms |
8852 KB |
Output is correct |
6 |
Correct |
14 ms |
8868 KB |
Output is correct |
7 |
Correct |
13 ms |
8868 KB |
Output is correct |
8 |
Correct |
22 ms |
11812 KB |
Output is correct |
9 |
Correct |
22 ms |
11940 KB |
Output is correct |
10 |
Correct |
22 ms |
11940 KB |
Output is correct |
11 |
Correct |
22 ms |
11940 KB |
Output is correct |
12 |
Correct |
16 ms |
11940 KB |
Output is correct |
13 |
Correct |
21 ms |
11940 KB |
Output is correct |
14 |
Correct |
19 ms |
11940 KB |
Output is correct |
15 |
Correct |
16 ms |
11940 KB |
Output is correct |
16 |
Correct |
19 ms |
11940 KB |
Output is correct |
17 |
Correct |
20 ms |
11940 KB |
Output is correct |
18 |
Correct |
17 ms |
11940 KB |
Output is correct |
19 |
Correct |
20 ms |
11940 KB |
Output is correct |
20 |
Correct |
847 ms |
16256 KB |
Output is correct |
21 |
Correct |
759 ms |
16264 KB |
Output is correct |
22 |
Correct |
838 ms |
16456 KB |
Output is correct |
23 |
Correct |
864 ms |
16456 KB |
Output is correct |
24 |
Correct |
1285 ms |
260656 KB |
Output is correct |
25 |
Correct |
1336 ms |
272188 KB |
Output is correct |
26 |
Correct |
1349 ms |
272188 KB |
Output is correct |
27 |
Correct |
1449 ms |
419384 KB |
Output is correct |
28 |
Correct |
1448 ms |
419384 KB |
Output is correct |
29 |
Correct |
1450 ms |
419384 KB |
Output is correct |
30 |
Correct |
1436 ms |
419384 KB |
Output is correct |
31 |
Correct |
1629 ms |
419384 KB |
Output is correct |
32 |
Correct |
1529 ms |
419384 KB |
Output is correct |
33 |
Correct |
1107 ms |
419384 KB |
Output is correct |
34 |
Correct |
1081 ms |
419384 KB |
Output is correct |
35 |
Correct |
1100 ms |
419384 KB |
Output is correct |
36 |
Correct |
1357 ms |
419384 KB |
Output is correct |
37 |
Correct |
1387 ms |
419384 KB |
Output is correct |
38 |
Correct |
1333 ms |
419384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
8184 KB |
Output is correct |
2 |
Correct |
9 ms |
8308 KB |
Output is correct |
3 |
Correct |
9 ms |
8308 KB |
Output is correct |
4 |
Correct |
9 ms |
8464 KB |
Output is correct |
5 |
Correct |
13 ms |
8852 KB |
Output is correct |
6 |
Correct |
14 ms |
8868 KB |
Output is correct |
7 |
Correct |
13 ms |
8868 KB |
Output is correct |
8 |
Correct |
22 ms |
11812 KB |
Output is correct |
9 |
Correct |
22 ms |
11940 KB |
Output is correct |
10 |
Correct |
22 ms |
11940 KB |
Output is correct |
11 |
Correct |
22 ms |
11940 KB |
Output is correct |
12 |
Correct |
16 ms |
11940 KB |
Output is correct |
13 |
Correct |
21 ms |
11940 KB |
Output is correct |
14 |
Correct |
19 ms |
11940 KB |
Output is correct |
15 |
Correct |
16 ms |
11940 KB |
Output is correct |
16 |
Correct |
19 ms |
11940 KB |
Output is correct |
17 |
Correct |
20 ms |
11940 KB |
Output is correct |
18 |
Correct |
17 ms |
11940 KB |
Output is correct |
19 |
Correct |
20 ms |
11940 KB |
Output is correct |
20 |
Correct |
847 ms |
16256 KB |
Output is correct |
21 |
Correct |
759 ms |
16264 KB |
Output is correct |
22 |
Correct |
838 ms |
16456 KB |
Output is correct |
23 |
Correct |
864 ms |
16456 KB |
Output is correct |
24 |
Correct |
1285 ms |
260656 KB |
Output is correct |
25 |
Correct |
1336 ms |
272188 KB |
Output is correct |
26 |
Correct |
1349 ms |
272188 KB |
Output is correct |
27 |
Correct |
1449 ms |
419384 KB |
Output is correct |
28 |
Correct |
1448 ms |
419384 KB |
Output is correct |
29 |
Correct |
1450 ms |
419384 KB |
Output is correct |
30 |
Correct |
1436 ms |
419384 KB |
Output is correct |
31 |
Correct |
1629 ms |
419384 KB |
Output is correct |
32 |
Correct |
1529 ms |
419384 KB |
Output is correct |
33 |
Correct |
1107 ms |
419384 KB |
Output is correct |
34 |
Correct |
1081 ms |
419384 KB |
Output is correct |
35 |
Correct |
1100 ms |
419384 KB |
Output is correct |
36 |
Correct |
1357 ms |
419384 KB |
Output is correct |
37 |
Correct |
1387 ms |
419384 KB |
Output is correct |
38 |
Correct |
1333 ms |
419384 KB |
Output is correct |
39 |
Correct |
1613 ms |
419384 KB |
Output is correct |
40 |
Correct |
1449 ms |
419384 KB |
Output is correct |
41 |
Correct |
1485 ms |
419384 KB |
Output is correct |
42 |
Correct |
1844 ms |
419384 KB |
Output is correct |
43 |
Correct |
1404 ms |
419384 KB |
Output is correct |
44 |
Correct |
876 ms |
419384 KB |
Output is correct |
45 |
Correct |
855 ms |
419384 KB |
Output is correct |
46 |
Correct |
837 ms |
419384 KB |
Output is correct |
47 |
Correct |
904 ms |
419384 KB |
Output is correct |
48 |
Correct |
851 ms |
419384 KB |
Output is correct |
49 |
Correct |
1737 ms |
419424 KB |
Output is correct |
50 |
Correct |
1666 ms |
419424 KB |
Output is correct |
51 |
Correct |
800 ms |
419424 KB |
Output is correct |
52 |
Correct |
788 ms |
419424 KB |
Output is correct |
53 |
Correct |
1650 ms |
419424 KB |
Output is correct |
54 |
Correct |
1687 ms |
419424 KB |
Output is correct |
55 |
Correct |
1593 ms |
419424 KB |
Output is correct |
56 |
Correct |
1510 ms |
419424 KB |
Output is correct |
57 |
Correct |
886 ms |
419424 KB |
Output is correct |
58 |
Correct |
881 ms |
419424 KB |
Output is correct |
59 |
Correct |
826 ms |
419424 KB |
Output is correct |
60 |
Correct |
835 ms |
419424 KB |
Output is correct |
61 |
Correct |
1786 ms |
419424 KB |
Output is correct |
62 |
Correct |
1631 ms |
419424 KB |
Output is correct |
63 |
Correct |
1630 ms |
419424 KB |
Output is correct |
64 |
Execution timed out |
2062 ms |
419528 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |