/**
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 = 100;
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 |
11 ms |
8308 KB |
Output is correct |
3 |
Correct |
8 ms |
8308 KB |
Output is correct |
4 |
Correct |
10 ms |
8460 KB |
Output is correct |
5 |
Correct |
15 ms |
8988 KB |
Output is correct |
6 |
Correct |
15 ms |
8988 KB |
Output is correct |
7 |
Correct |
15 ms |
8988 KB |
Output is correct |
8 |
Correct |
16 ms |
9432 KB |
Output is correct |
9 |
Correct |
16 ms |
9452 KB |
Output is correct |
10 |
Correct |
16 ms |
9452 KB |
Output is correct |
11 |
Correct |
16 ms |
9452 KB |
Output is correct |
12 |
Correct |
16 ms |
9452 KB |
Output is correct |
13 |
Correct |
17 ms |
9724 KB |
Output is correct |
14 |
Correct |
16 ms |
9724 KB |
Output is correct |
15 |
Correct |
14 ms |
9724 KB |
Output is correct |
16 |
Correct |
14 ms |
9724 KB |
Output is correct |
17 |
Correct |
14 ms |
9724 KB |
Output is correct |
18 |
Correct |
15 ms |
9724 KB |
Output is correct |
19 |
Correct |
14 ms |
9724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
8184 KB |
Output is correct |
2 |
Correct |
11 ms |
8308 KB |
Output is correct |
3 |
Correct |
8 ms |
8308 KB |
Output is correct |
4 |
Correct |
10 ms |
8460 KB |
Output is correct |
5 |
Correct |
15 ms |
8988 KB |
Output is correct |
6 |
Correct |
15 ms |
8988 KB |
Output is correct |
7 |
Correct |
15 ms |
8988 KB |
Output is correct |
8 |
Correct |
16 ms |
9432 KB |
Output is correct |
9 |
Correct |
16 ms |
9452 KB |
Output is correct |
10 |
Correct |
16 ms |
9452 KB |
Output is correct |
11 |
Correct |
16 ms |
9452 KB |
Output is correct |
12 |
Correct |
16 ms |
9452 KB |
Output is correct |
13 |
Correct |
17 ms |
9724 KB |
Output is correct |
14 |
Correct |
16 ms |
9724 KB |
Output is correct |
15 |
Correct |
14 ms |
9724 KB |
Output is correct |
16 |
Correct |
14 ms |
9724 KB |
Output is correct |
17 |
Correct |
14 ms |
9724 KB |
Output is correct |
18 |
Correct |
15 ms |
9724 KB |
Output is correct |
19 |
Correct |
14 ms |
9724 KB |
Output is correct |
20 |
Correct |
376 ms |
13824 KB |
Output is correct |
21 |
Correct |
356 ms |
13844 KB |
Output is correct |
22 |
Correct |
371 ms |
13868 KB |
Output is correct |
23 |
Correct |
377 ms |
13872 KB |
Output is correct |
24 |
Correct |
752 ms |
93324 KB |
Output is correct |
25 |
Correct |
756 ms |
94460 KB |
Output is correct |
26 |
Correct |
752 ms |
94460 KB |
Output is correct |
27 |
Correct |
837 ms |
119244 KB |
Output is correct |
28 |
Correct |
847 ms |
119304 KB |
Output is correct |
29 |
Correct |
818 ms |
119304 KB |
Output is correct |
30 |
Correct |
807 ms |
119304 KB |
Output is correct |
31 |
Correct |
794 ms |
119304 KB |
Output is correct |
32 |
Correct |
752 ms |
119304 KB |
Output is correct |
33 |
Correct |
610 ms |
119304 KB |
Output is correct |
34 |
Correct |
587 ms |
119304 KB |
Output is correct |
35 |
Correct |
664 ms |
119304 KB |
Output is correct |
36 |
Correct |
712 ms |
119304 KB |
Output is correct |
37 |
Correct |
652 ms |
119304 KB |
Output is correct |
38 |
Correct |
709 ms |
119304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
8184 KB |
Output is correct |
2 |
Correct |
11 ms |
8308 KB |
Output is correct |
3 |
Correct |
8 ms |
8308 KB |
Output is correct |
4 |
Correct |
10 ms |
8460 KB |
Output is correct |
5 |
Correct |
15 ms |
8988 KB |
Output is correct |
6 |
Correct |
15 ms |
8988 KB |
Output is correct |
7 |
Correct |
15 ms |
8988 KB |
Output is correct |
8 |
Correct |
16 ms |
9432 KB |
Output is correct |
9 |
Correct |
16 ms |
9452 KB |
Output is correct |
10 |
Correct |
16 ms |
9452 KB |
Output is correct |
11 |
Correct |
16 ms |
9452 KB |
Output is correct |
12 |
Correct |
16 ms |
9452 KB |
Output is correct |
13 |
Correct |
17 ms |
9724 KB |
Output is correct |
14 |
Correct |
16 ms |
9724 KB |
Output is correct |
15 |
Correct |
14 ms |
9724 KB |
Output is correct |
16 |
Correct |
14 ms |
9724 KB |
Output is correct |
17 |
Correct |
14 ms |
9724 KB |
Output is correct |
18 |
Correct |
15 ms |
9724 KB |
Output is correct |
19 |
Correct |
14 ms |
9724 KB |
Output is correct |
20 |
Correct |
376 ms |
13824 KB |
Output is correct |
21 |
Correct |
356 ms |
13844 KB |
Output is correct |
22 |
Correct |
371 ms |
13868 KB |
Output is correct |
23 |
Correct |
377 ms |
13872 KB |
Output is correct |
24 |
Correct |
752 ms |
93324 KB |
Output is correct |
25 |
Correct |
756 ms |
94460 KB |
Output is correct |
26 |
Correct |
752 ms |
94460 KB |
Output is correct |
27 |
Correct |
837 ms |
119244 KB |
Output is correct |
28 |
Correct |
847 ms |
119304 KB |
Output is correct |
29 |
Correct |
818 ms |
119304 KB |
Output is correct |
30 |
Correct |
807 ms |
119304 KB |
Output is correct |
31 |
Correct |
794 ms |
119304 KB |
Output is correct |
32 |
Correct |
752 ms |
119304 KB |
Output is correct |
33 |
Correct |
610 ms |
119304 KB |
Output is correct |
34 |
Correct |
587 ms |
119304 KB |
Output is correct |
35 |
Correct |
664 ms |
119304 KB |
Output is correct |
36 |
Correct |
712 ms |
119304 KB |
Output is correct |
37 |
Correct |
652 ms |
119304 KB |
Output is correct |
38 |
Correct |
709 ms |
119304 KB |
Output is correct |
39 |
Correct |
983 ms |
119304 KB |
Output is correct |
40 |
Correct |
932 ms |
119304 KB |
Output is correct |
41 |
Execution timed out |
2017 ms |
119304 KB |
Time limit exceeded |
42 |
Halted |
0 ms |
0 KB |
- |