/**
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;
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()) {
~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
8184 KB |
Output is correct |
2 |
Correct |
10 ms |
8252 KB |
Output is correct |
3 |
Correct |
11 ms |
8476 KB |
Output is correct |
4 |
Correct |
10 ms |
8476 KB |
Output is correct |
5 |
Correct |
14 ms |
8756 KB |
Output is correct |
6 |
Correct |
15 ms |
8756 KB |
Output is correct |
7 |
Correct |
14 ms |
8796 KB |
Output is correct |
8 |
Correct |
25 ms |
11768 KB |
Output is correct |
9 |
Correct |
24 ms |
11808 KB |
Output is correct |
10 |
Correct |
24 ms |
11936 KB |
Output is correct |
11 |
Correct |
23 ms |
11936 KB |
Output is correct |
12 |
Correct |
18 ms |
11936 KB |
Output is correct |
13 |
Correct |
24 ms |
11936 KB |
Output is correct |
14 |
Correct |
20 ms |
11936 KB |
Output is correct |
15 |
Correct |
17 ms |
11936 KB |
Output is correct |
16 |
Correct |
20 ms |
11936 KB |
Output is correct |
17 |
Correct |
20 ms |
11936 KB |
Output is correct |
18 |
Correct |
18 ms |
11936 KB |
Output is correct |
19 |
Correct |
21 ms |
11936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
8184 KB |
Output is correct |
2 |
Correct |
10 ms |
8252 KB |
Output is correct |
3 |
Correct |
11 ms |
8476 KB |
Output is correct |
4 |
Correct |
10 ms |
8476 KB |
Output is correct |
5 |
Correct |
14 ms |
8756 KB |
Output is correct |
6 |
Correct |
15 ms |
8756 KB |
Output is correct |
7 |
Correct |
14 ms |
8796 KB |
Output is correct |
8 |
Correct |
25 ms |
11768 KB |
Output is correct |
9 |
Correct |
24 ms |
11808 KB |
Output is correct |
10 |
Correct |
24 ms |
11936 KB |
Output is correct |
11 |
Correct |
23 ms |
11936 KB |
Output is correct |
12 |
Correct |
18 ms |
11936 KB |
Output is correct |
13 |
Correct |
24 ms |
11936 KB |
Output is correct |
14 |
Correct |
20 ms |
11936 KB |
Output is correct |
15 |
Correct |
17 ms |
11936 KB |
Output is correct |
16 |
Correct |
20 ms |
11936 KB |
Output is correct |
17 |
Correct |
20 ms |
11936 KB |
Output is correct |
18 |
Correct |
18 ms |
11936 KB |
Output is correct |
19 |
Correct |
21 ms |
11936 KB |
Output is correct |
20 |
Correct |
808 ms |
16272 KB |
Output is correct |
21 |
Correct |
753 ms |
16272 KB |
Output is correct |
22 |
Correct |
845 ms |
16272 KB |
Output is correct |
23 |
Correct |
870 ms |
16272 KB |
Output is correct |
24 |
Correct |
1408 ms |
260188 KB |
Output is correct |
25 |
Correct |
1351 ms |
271788 KB |
Output is correct |
26 |
Correct |
1427 ms |
271788 KB |
Output is correct |
27 |
Correct |
1393 ms |
419340 KB |
Output is correct |
28 |
Correct |
1545 ms |
419416 KB |
Output is correct |
29 |
Correct |
1539 ms |
419656 KB |
Output is correct |
30 |
Correct |
1446 ms |
419656 KB |
Output is correct |
31 |
Correct |
1436 ms |
419656 KB |
Output is correct |
32 |
Correct |
1422 ms |
419656 KB |
Output is correct |
33 |
Correct |
1178 ms |
419656 KB |
Output is correct |
34 |
Correct |
1065 ms |
419656 KB |
Output is correct |
35 |
Correct |
1106 ms |
419656 KB |
Output is correct |
36 |
Correct |
1282 ms |
419656 KB |
Output is correct |
37 |
Correct |
1301 ms |
419656 KB |
Output is correct |
38 |
Correct |
1277 ms |
419656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
8184 KB |
Output is correct |
2 |
Correct |
10 ms |
8252 KB |
Output is correct |
3 |
Correct |
11 ms |
8476 KB |
Output is correct |
4 |
Correct |
10 ms |
8476 KB |
Output is correct |
5 |
Correct |
14 ms |
8756 KB |
Output is correct |
6 |
Correct |
15 ms |
8756 KB |
Output is correct |
7 |
Correct |
14 ms |
8796 KB |
Output is correct |
8 |
Correct |
25 ms |
11768 KB |
Output is correct |
9 |
Correct |
24 ms |
11808 KB |
Output is correct |
10 |
Correct |
24 ms |
11936 KB |
Output is correct |
11 |
Correct |
23 ms |
11936 KB |
Output is correct |
12 |
Correct |
18 ms |
11936 KB |
Output is correct |
13 |
Correct |
24 ms |
11936 KB |
Output is correct |
14 |
Correct |
20 ms |
11936 KB |
Output is correct |
15 |
Correct |
17 ms |
11936 KB |
Output is correct |
16 |
Correct |
20 ms |
11936 KB |
Output is correct |
17 |
Correct |
20 ms |
11936 KB |
Output is correct |
18 |
Correct |
18 ms |
11936 KB |
Output is correct |
19 |
Correct |
21 ms |
11936 KB |
Output is correct |
20 |
Correct |
808 ms |
16272 KB |
Output is correct |
21 |
Correct |
753 ms |
16272 KB |
Output is correct |
22 |
Correct |
845 ms |
16272 KB |
Output is correct |
23 |
Correct |
870 ms |
16272 KB |
Output is correct |
24 |
Correct |
1408 ms |
260188 KB |
Output is correct |
25 |
Correct |
1351 ms |
271788 KB |
Output is correct |
26 |
Correct |
1427 ms |
271788 KB |
Output is correct |
27 |
Correct |
1393 ms |
419340 KB |
Output is correct |
28 |
Correct |
1545 ms |
419416 KB |
Output is correct |
29 |
Correct |
1539 ms |
419656 KB |
Output is correct |
30 |
Correct |
1446 ms |
419656 KB |
Output is correct |
31 |
Correct |
1436 ms |
419656 KB |
Output is correct |
32 |
Correct |
1422 ms |
419656 KB |
Output is correct |
33 |
Correct |
1178 ms |
419656 KB |
Output is correct |
34 |
Correct |
1065 ms |
419656 KB |
Output is correct |
35 |
Correct |
1106 ms |
419656 KB |
Output is correct |
36 |
Correct |
1282 ms |
419656 KB |
Output is correct |
37 |
Correct |
1301 ms |
419656 KB |
Output is correct |
38 |
Correct |
1277 ms |
419656 KB |
Output is correct |
39 |
Correct |
1616 ms |
419656 KB |
Output is correct |
40 |
Correct |
1531 ms |
419656 KB |
Output is correct |
41 |
Correct |
1595 ms |
419656 KB |
Output is correct |
42 |
Correct |
1753 ms |
419656 KB |
Output is correct |
43 |
Correct |
1400 ms |
419656 KB |
Output is correct |
44 |
Correct |
849 ms |
419656 KB |
Output is correct |
45 |
Correct |
807 ms |
419656 KB |
Output is correct |
46 |
Correct |
818 ms |
419656 KB |
Output is correct |
47 |
Correct |
876 ms |
419656 KB |
Output is correct |
48 |
Correct |
858 ms |
419656 KB |
Output is correct |
49 |
Correct |
1747 ms |
420160 KB |
Output is correct |
50 |
Correct |
1650 ms |
420160 KB |
Output is correct |
51 |
Correct |
772 ms |
420160 KB |
Output is correct |
52 |
Correct |
746 ms |
420160 KB |
Output is correct |
53 |
Correct |
1575 ms |
420160 KB |
Output is correct |
54 |
Correct |
1576 ms |
420160 KB |
Output is correct |
55 |
Correct |
1536 ms |
420160 KB |
Output is correct |
56 |
Correct |
1471 ms |
420160 KB |
Output is correct |
57 |
Correct |
828 ms |
420160 KB |
Output is correct |
58 |
Correct |
891 ms |
420160 KB |
Output is correct |
59 |
Correct |
828 ms |
420160 KB |
Output is correct |
60 |
Correct |
851 ms |
420160 KB |
Output is correct |
61 |
Correct |
1795 ms |
420160 KB |
Output is correct |
62 |
Correct |
1613 ms |
420160 KB |
Output is correct |
63 |
Correct |
1552 ms |
420160 KB |
Output is correct |
64 |
Execution timed out |
2086 ms |
420308 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |