#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Query{
int town, idx;
vector<int> busy;
bool operator < (const Query &o) const { return town < o.town; }
};
int dp[N], out[N];
set<pair<int, int>, greater<pair<int, int>>> s[N];
set<int, greater<int>> rev[N];
vector<int> adj[N];
vector<Query> que;
int main() {
int n, m, Q, a, b, n_busy;
scanf(" %d %d %d", &n, &m, &Q);
int sq = ceil(sqrt(n+.0));
while (m--) {
scanf(" %d %d", &a, &b);
rev[max(a, b)].insert(min(a, b));
adj[min(a, b)].push_back(max(a, b));
}
for (int i=1; i<=Q; i++) {
Query in;
in.idx = i;
scanf(" %d %d", &in.town, &n_busy);
while (n_busy--) {
scanf(" %d", &a);
in.busy.push_back(a);
}
que.push_back(in);
}
sort(que.begin(), que.end());
int now = 1;
for (int i=1; i<=n; i++) s[i].insert({0, i});
fill_n(out, n+5, -1);
for (auto q : que) {
while (now < q.town) {
now++;
for (auto to : rev[now]) {
for (auto [val, from] : s[to]) {
auto tmp = s[now].end();
tmp--;
if (s[now].size() < sq) s[now].insert({val+1, from});
else if (val+1 > tmp->first) {
s[now].erase(tmp);
s[now].insert({val+1, from});
}
else break;
}
}
}
if (q.busy.size() >= sq) {
fill_n(dp, q.town+5, 0);
for (auto it : q.busy) dp[it] = -1;
for (int i=1; i<=q.town; i++) {
if (dp[i] == -1) continue;
for (auto to : adj[i]) dp[to] = max(dp[to], dp[i] + 1);
}
out[q.idx] = dp[q.town];
}
else {
for (auto [val, from] : s[now]) {
auto tmp = lower_bound(q.busy.begin(), q.busy.end(), from);
if (tmp == q.busy.end() || *tmp != from) {
out[q.idx] = val;
break;
}
}
}
}
/*
for (int i=1; i<=n; i++) {
printf("set %d : ", i);
for (auto it : s[i]) printf("(%d %d) ", it.first, it.second);
printf("\n");
}
*/
for (int i=1; i<=Q; i++) printf("%d\n", out[i]);
return 0;
}
Compilation message
bitaro.cpp: In function 'int main()':
bitaro.cpp:48:39: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int>, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | if (s[now].size() < sq) s[now].insert({val+1, from});
| ~~~~~~~~~~~~~~^~~~
bitaro.cpp:57:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
57 | if (q.busy.size() >= sq) {
| ~~~~~~~~~~~~~~^~~~~
bitaro.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf(" %d %d %d", &n, &m, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf(" %d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf(" %d %d", &in.town, &n_busy);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf(" %d", &a);
| ~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
11980 KB |
Output is correct |
3 |
Correct |
6 ms |
11980 KB |
Output is correct |
4 |
Correct |
6 ms |
11980 KB |
Output is correct |
5 |
Correct |
7 ms |
12492 KB |
Output is correct |
6 |
Correct |
10 ms |
13136 KB |
Output is correct |
7 |
Correct |
10 ms |
13132 KB |
Output is correct |
8 |
Correct |
7 ms |
12364 KB |
Output is correct |
9 |
Correct |
9 ms |
13132 KB |
Output is correct |
10 |
Correct |
12 ms |
13056 KB |
Output is correct |
11 |
Correct |
7 ms |
12236 KB |
Output is correct |
12 |
Correct |
8 ms |
12364 KB |
Output is correct |
13 |
Correct |
7 ms |
12236 KB |
Output is correct |
14 |
Correct |
7 ms |
12308 KB |
Output is correct |
15 |
Correct |
7 ms |
12236 KB |
Output is correct |
16 |
Correct |
9 ms |
12944 KB |
Output is correct |
17 |
Correct |
8 ms |
12580 KB |
Output is correct |
18 |
Correct |
8 ms |
12288 KB |
Output is correct |
19 |
Correct |
10 ms |
13184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
11980 KB |
Output is correct |
3 |
Correct |
6 ms |
11980 KB |
Output is correct |
4 |
Correct |
6 ms |
11980 KB |
Output is correct |
5 |
Correct |
7 ms |
12492 KB |
Output is correct |
6 |
Correct |
10 ms |
13136 KB |
Output is correct |
7 |
Correct |
10 ms |
13132 KB |
Output is correct |
8 |
Correct |
7 ms |
12364 KB |
Output is correct |
9 |
Correct |
9 ms |
13132 KB |
Output is correct |
10 |
Correct |
12 ms |
13056 KB |
Output is correct |
11 |
Correct |
7 ms |
12236 KB |
Output is correct |
12 |
Correct |
8 ms |
12364 KB |
Output is correct |
13 |
Correct |
7 ms |
12236 KB |
Output is correct |
14 |
Correct |
7 ms |
12308 KB |
Output is correct |
15 |
Correct |
7 ms |
12236 KB |
Output is correct |
16 |
Correct |
9 ms |
12944 KB |
Output is correct |
17 |
Correct |
8 ms |
12580 KB |
Output is correct |
18 |
Correct |
8 ms |
12288 KB |
Output is correct |
19 |
Correct |
10 ms |
13184 KB |
Output is correct |
20 |
Correct |
122 ms |
23392 KB |
Output is correct |
21 |
Correct |
127 ms |
23068 KB |
Output is correct |
22 |
Correct |
161 ms |
23988 KB |
Output is correct |
23 |
Correct |
116 ms |
23000 KB |
Output is correct |
24 |
Runtime error |
1880 ms |
524292 KB |
Execution killed with signal 9 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
11980 KB |
Output is correct |
3 |
Correct |
6 ms |
11980 KB |
Output is correct |
4 |
Correct |
6 ms |
11980 KB |
Output is correct |
5 |
Correct |
7 ms |
12492 KB |
Output is correct |
6 |
Correct |
10 ms |
13136 KB |
Output is correct |
7 |
Correct |
10 ms |
13132 KB |
Output is correct |
8 |
Correct |
7 ms |
12364 KB |
Output is correct |
9 |
Correct |
9 ms |
13132 KB |
Output is correct |
10 |
Correct |
12 ms |
13056 KB |
Output is correct |
11 |
Correct |
7 ms |
12236 KB |
Output is correct |
12 |
Correct |
8 ms |
12364 KB |
Output is correct |
13 |
Correct |
7 ms |
12236 KB |
Output is correct |
14 |
Correct |
7 ms |
12308 KB |
Output is correct |
15 |
Correct |
7 ms |
12236 KB |
Output is correct |
16 |
Correct |
9 ms |
12944 KB |
Output is correct |
17 |
Correct |
8 ms |
12580 KB |
Output is correct |
18 |
Correct |
8 ms |
12288 KB |
Output is correct |
19 |
Correct |
10 ms |
13184 KB |
Output is correct |
20 |
Correct |
122 ms |
23392 KB |
Output is correct |
21 |
Correct |
127 ms |
23068 KB |
Output is correct |
22 |
Correct |
161 ms |
23988 KB |
Output is correct |
23 |
Correct |
116 ms |
23000 KB |
Output is correct |
24 |
Runtime error |
1880 ms |
524292 KB |
Execution killed with signal 9 |
25 |
Halted |
0 ms |
0 KB |
- |