/**
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 = 300;
const int32_t INF = 2e9;
std::bitset< MAX_N + 5 > isInVector;
std::bitset< MAX_N + 5 > isForbidden;
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 + 1) {
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].first + 1, v2[ind2].second });
}
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].first + 1, v2[ind2].second });
}
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;
};
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]);
}
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) {
nodes[i].dp = Merge(nodes[i].dp, x->dp);
}
}
}
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);
for(int32_t i = 1; i <= t; i++) {
if(isForbidden[i]) {
dp[i] = -INF;
}
else {
dp[i] = 0;
}
for(auto &x : nodes[i].v) {
dp[i] = std::max(dp[i], dp[x->id] + 1);
}
}
return std::max(dp[t], -1);
}
};
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:21:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
~~~~~^~~~~~~~~~~
bitaro.cpp:21:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
~~~~~^~~~~~~~~~~
bitaro.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind1 < v1.size()) {
~~~~~^~~~~~~~~~~
bitaro.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind2 < v2.size()) {
~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5752 KB |
Output is correct |
2 |
Correct |
7 ms |
5876 KB |
Output is correct |
3 |
Correct |
7 ms |
5876 KB |
Output is correct |
4 |
Correct |
8 ms |
5912 KB |
Output is correct |
5 |
Correct |
14 ms |
6484 KB |
Output is correct |
6 |
Correct |
13 ms |
6560 KB |
Output is correct |
7 |
Correct |
11 ms |
6708 KB |
Output is correct |
8 |
Correct |
23 ms |
9372 KB |
Output is correct |
9 |
Correct |
23 ms |
9440 KB |
Output is correct |
10 |
Correct |
23 ms |
9440 KB |
Output is correct |
11 |
Correct |
22 ms |
9440 KB |
Output is correct |
12 |
Correct |
16 ms |
9440 KB |
Output is correct |
13 |
Correct |
22 ms |
9440 KB |
Output is correct |
14 |
Correct |
20 ms |
9440 KB |
Output is correct |
15 |
Correct |
13 ms |
9440 KB |
Output is correct |
16 |
Correct |
20 ms |
9440 KB |
Output is correct |
17 |
Correct |
19 ms |
9440 KB |
Output is correct |
18 |
Correct |
15 ms |
9440 KB |
Output is correct |
19 |
Correct |
19 ms |
9440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5752 KB |
Output is correct |
2 |
Correct |
7 ms |
5876 KB |
Output is correct |
3 |
Correct |
7 ms |
5876 KB |
Output is correct |
4 |
Correct |
8 ms |
5912 KB |
Output is correct |
5 |
Correct |
14 ms |
6484 KB |
Output is correct |
6 |
Correct |
13 ms |
6560 KB |
Output is correct |
7 |
Correct |
11 ms |
6708 KB |
Output is correct |
8 |
Correct |
23 ms |
9372 KB |
Output is correct |
9 |
Correct |
23 ms |
9440 KB |
Output is correct |
10 |
Correct |
23 ms |
9440 KB |
Output is correct |
11 |
Correct |
22 ms |
9440 KB |
Output is correct |
12 |
Correct |
16 ms |
9440 KB |
Output is correct |
13 |
Correct |
22 ms |
9440 KB |
Output is correct |
14 |
Correct |
20 ms |
9440 KB |
Output is correct |
15 |
Correct |
13 ms |
9440 KB |
Output is correct |
16 |
Correct |
20 ms |
9440 KB |
Output is correct |
17 |
Correct |
19 ms |
9440 KB |
Output is correct |
18 |
Correct |
15 ms |
9440 KB |
Output is correct |
19 |
Correct |
19 ms |
9440 KB |
Output is correct |
20 |
Correct |
847 ms |
11696 KB |
Output is correct |
21 |
Correct |
777 ms |
11696 KB |
Output is correct |
22 |
Correct |
854 ms |
11744 KB |
Output is correct |
23 |
Correct |
903 ms |
11744 KB |
Output is correct |
24 |
Correct |
1483 ms |
253520 KB |
Output is correct |
25 |
Correct |
1605 ms |
265036 KB |
Output is correct |
26 |
Correct |
1364 ms |
265036 KB |
Output is correct |
27 |
Correct |
1507 ms |
412440 KB |
Output is correct |
28 |
Correct |
1517 ms |
412484 KB |
Output is correct |
29 |
Correct |
1534 ms |
412640 KB |
Output is correct |
30 |
Correct |
1548 ms |
412640 KB |
Output is correct |
31 |
Correct |
1501 ms |
412640 KB |
Output is correct |
32 |
Correct |
1447 ms |
412640 KB |
Output is correct |
33 |
Correct |
1180 ms |
412640 KB |
Output is correct |
34 |
Correct |
1052 ms |
412640 KB |
Output is correct |
35 |
Correct |
1162 ms |
412640 KB |
Output is correct |
36 |
Correct |
1381 ms |
412640 KB |
Output is correct |
37 |
Correct |
1385 ms |
412640 KB |
Output is correct |
38 |
Correct |
1485 ms |
412640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5752 KB |
Output is correct |
2 |
Correct |
7 ms |
5876 KB |
Output is correct |
3 |
Correct |
7 ms |
5876 KB |
Output is correct |
4 |
Correct |
8 ms |
5912 KB |
Output is correct |
5 |
Correct |
14 ms |
6484 KB |
Output is correct |
6 |
Correct |
13 ms |
6560 KB |
Output is correct |
7 |
Correct |
11 ms |
6708 KB |
Output is correct |
8 |
Correct |
23 ms |
9372 KB |
Output is correct |
9 |
Correct |
23 ms |
9440 KB |
Output is correct |
10 |
Correct |
23 ms |
9440 KB |
Output is correct |
11 |
Correct |
22 ms |
9440 KB |
Output is correct |
12 |
Correct |
16 ms |
9440 KB |
Output is correct |
13 |
Correct |
22 ms |
9440 KB |
Output is correct |
14 |
Correct |
20 ms |
9440 KB |
Output is correct |
15 |
Correct |
13 ms |
9440 KB |
Output is correct |
16 |
Correct |
20 ms |
9440 KB |
Output is correct |
17 |
Correct |
19 ms |
9440 KB |
Output is correct |
18 |
Correct |
15 ms |
9440 KB |
Output is correct |
19 |
Correct |
19 ms |
9440 KB |
Output is correct |
20 |
Correct |
847 ms |
11696 KB |
Output is correct |
21 |
Correct |
777 ms |
11696 KB |
Output is correct |
22 |
Correct |
854 ms |
11744 KB |
Output is correct |
23 |
Correct |
903 ms |
11744 KB |
Output is correct |
24 |
Correct |
1483 ms |
253520 KB |
Output is correct |
25 |
Correct |
1605 ms |
265036 KB |
Output is correct |
26 |
Correct |
1364 ms |
265036 KB |
Output is correct |
27 |
Correct |
1507 ms |
412440 KB |
Output is correct |
28 |
Correct |
1517 ms |
412484 KB |
Output is correct |
29 |
Correct |
1534 ms |
412640 KB |
Output is correct |
30 |
Correct |
1548 ms |
412640 KB |
Output is correct |
31 |
Correct |
1501 ms |
412640 KB |
Output is correct |
32 |
Correct |
1447 ms |
412640 KB |
Output is correct |
33 |
Correct |
1180 ms |
412640 KB |
Output is correct |
34 |
Correct |
1052 ms |
412640 KB |
Output is correct |
35 |
Correct |
1162 ms |
412640 KB |
Output is correct |
36 |
Correct |
1381 ms |
412640 KB |
Output is correct |
37 |
Correct |
1385 ms |
412640 KB |
Output is correct |
38 |
Correct |
1485 ms |
412640 KB |
Output is correct |
39 |
Correct |
1809 ms |
412640 KB |
Output is correct |
40 |
Correct |
1807 ms |
412640 KB |
Output is correct |
41 |
Correct |
1842 ms |
412640 KB |
Output is correct |
42 |
Correct |
1676 ms |
412640 KB |
Output is correct |
43 |
Correct |
1587 ms |
412640 KB |
Output is correct |
44 |
Correct |
897 ms |
412640 KB |
Output is correct |
45 |
Correct |
852 ms |
412640 KB |
Output is correct |
46 |
Correct |
881 ms |
412640 KB |
Output is correct |
47 |
Correct |
869 ms |
412640 KB |
Output is correct |
48 |
Correct |
868 ms |
412640 KB |
Output is correct |
49 |
Correct |
1989 ms |
412640 KB |
Output is correct |
50 |
Correct |
1888 ms |
412640 KB |
Output is correct |
51 |
Correct |
839 ms |
412640 KB |
Output is correct |
52 |
Correct |
819 ms |
412640 KB |
Output is correct |
53 |
Correct |
1790 ms |
412640 KB |
Output is correct |
54 |
Correct |
1666 ms |
412640 KB |
Output is correct |
55 |
Correct |
1688 ms |
412640 KB |
Output is correct |
56 |
Correct |
1650 ms |
412640 KB |
Output is correct |
57 |
Correct |
889 ms |
412640 KB |
Output is correct |
58 |
Correct |
914 ms |
412640 KB |
Output is correct |
59 |
Correct |
856 ms |
412640 KB |
Output is correct |
60 |
Correct |
856 ms |
412640 KB |
Output is correct |
61 |
Correct |
1712 ms |
412640 KB |
Output is correct |
62 |
Correct |
1647 ms |
412640 KB |
Output is correct |
63 |
Correct |
1552 ms |
412640 KB |
Output is correct |
64 |
Correct |
1918 ms |
412892 KB |
Output is correct |
65 |
Correct |
1877 ms |
412892 KB |
Output is correct |
66 |
Correct |
1932 ms |
412892 KB |
Output is correct |
67 |
Correct |
1908 ms |
412892 KB |
Output is correct |
68 |
Correct |
1733 ms |
412892 KB |
Output is correct |
69 |
Correct |
1633 ms |
412892 KB |
Output is correct |
70 |
Correct |
1638 ms |
412964 KB |
Output is correct |
71 |
Correct |
1488 ms |
412964 KB |
Output is correct |
72 |
Correct |
1341 ms |
412964 KB |
Output is correct |
73 |
Correct |
1534 ms |
413076 KB |
Output is correct |
74 |
Correct |
1449 ms |
413076 KB |
Output is correct |
75 |
Correct |
1445 ms |
413076 KB |
Output is correct |
76 |
Correct |
1857 ms |
413224 KB |
Output is correct |
77 |
Correct |
1819 ms |
413224 KB |
Output is correct |
78 |
Correct |
1661 ms |
413224 KB |
Output is correct |
79 |
Correct |
844 ms |
413224 KB |
Output is correct |
80 |
Correct |
845 ms |
413224 KB |
Output is correct |
81 |
Correct |
777 ms |
413224 KB |
Output is correct |
82 |
Correct |
1838 ms |
413224 KB |
Output is correct |
83 |
Correct |
1852 ms |
413224 KB |
Output is correct |
84 |
Correct |
1756 ms |
413224 KB |
Output is correct |
85 |
Correct |
1817 ms |
413224 KB |
Output is correct |
86 |
Correct |
1489 ms |
413224 KB |
Output is correct |
87 |
Correct |
1631 ms |
413224 KB |
Output is correct |
88 |
Correct |
905 ms |
413224 KB |
Output is correct |
89 |
Correct |
891 ms |
413224 KB |
Output is correct |
90 |
Correct |
826 ms |
413224 KB |
Output is correct |
91 |
Correct |
865 ms |
413224 KB |
Output is correct |
92 |
Correct |
848 ms |
413224 KB |
Output is correct |
93 |
Correct |
842 ms |
413224 KB |
Output is correct |
94 |
Correct |
1412 ms |
413224 KB |
Output is correct |
95 |
Correct |
1204 ms |
413224 KB |
Output is correct |
96 |
Correct |
1379 ms |
413224 KB |
Output is correct |
97 |
Correct |
1267 ms |
413224 KB |
Output is correct |
98 |
Correct |
1212 ms |
413224 KB |
Output is correct |
99 |
Correct |
1058 ms |
413224 KB |
Output is correct |
100 |
Correct |
902 ms |
413224 KB |
Output is correct |
101 |
Correct |
894 ms |
413224 KB |
Output is correct |
102 |
Correct |
866 ms |
413224 KB |
Output is correct |
103 |
Correct |
898 ms |
413224 KB |
Output is correct |
104 |
Correct |
877 ms |
413224 KB |
Output is correct |
105 |
Correct |
886 ms |
413224 KB |
Output is correct |
106 |
Correct |
1683 ms |
413224 KB |
Output is correct |
107 |
Correct |
1645 ms |
413224 KB |
Output is correct |
108 |
Correct |
1594 ms |
413224 KB |
Output is correct |
109 |
Correct |
1509 ms |
413224 KB |
Output is correct |
110 |
Correct |
1389 ms |
413224 KB |
Output is correct |
111 |
Correct |
1397 ms |
413224 KB |
Output is correct |
112 |
Correct |
881 ms |
413224 KB |
Output is correct |
113 |
Correct |
902 ms |
413224 KB |
Output is correct |
114 |
Correct |
840 ms |
413224 KB |
Output is correct |
115 |
Correct |
889 ms |
413224 KB |
Output is correct |
116 |
Correct |
830 ms |
413224 KB |
Output is correct |
117 |
Correct |
868 ms |
413224 KB |
Output is correct |
118 |
Correct |
1886 ms |
413224 KB |
Output is correct |
119 |
Correct |
1588 ms |
413224 KB |
Output is correct |
120 |
Correct |
1640 ms |
413224 KB |
Output is correct |
121 |
Correct |
1826 ms |
413224 KB |
Output is correct |
122 |
Correct |
1635 ms |
413224 KB |
Output is correct |
123 |
Correct |
1501 ms |
413224 KB |
Output is correct |
124 |
Correct |
1772 ms |
413224 KB |
Output is correct |
125 |
Correct |
1715 ms |
413224 KB |
Output is correct |
126 |
Correct |
1577 ms |
413224 KB |
Output is correct |