#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
const int srt = 310;
struct query {
int id;
vector<int> block;
query() : id(0) {}
query (int x, vector<int> v) : id(x), block(v) {}
};
vector<int> adj[mn], rev[mn], line, lineRev;
bool vis[mn], check[mn];
void dfs (int u) {
if (vis[u]) return;
vis[u] = 1;
for (int v : adj[u]) dfs(v);
line.push_back(u);
}
void dfsRev (int u) {
if (vis[u]) return;
vis[u] = 1;
for (int v : rev[u]) dfsRev(v);
lineRev.push_back(u);
}
vector<query> qry[mn];
vector<pii> best[mn];
int dp[mn], ans[mn], iter[mn], n;
bool compare (pii a, pii b) { return a.first > b.first; }
void process (int u) {
int cnt = 0;
for (int v : rev[u]) {
if (best[v].size()) cnt++;
iter[v] = 0;
}
while (cnt && best[u].size() < srt) {
int ans = INT_MIN, save = 0;
for (int v : rev[u]) {
if (iter[v] == best[v].size()) continue;
int dist, node; tie(dist, node) = best[v][iter[v]];
if (dist + 1 > ans) ans = dist + 1, save = v;
}
int dist, node; tie(dist, node) = best[save][iter[save]++];
best[u].push_back(make_pair(dist + 1, node));
if (iter[save] == best[save].size()) cnt--;
}
if (best[u].size() < srt)
best[u].push_back(make_pair(0, u));
}
int dpCalc (int st, vector<int> &block) {
for (int u : block) check[u] = 1;
for (int i = 1; i <= n; i++) dp[i] = INT_MIN;
dp[st] = 0; int ans = INT_MIN;
for (int u : lineRev) {
for (int v : adj[u])
if (dp[v] != INT_MIN) dp[u] = max(dp[u], dp[v] + 1);
if (!check[u]) ans = max(ans, dp[u]);
}
for (int u : block) check[u] = 0;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int m, q; cin >> n >> m >> q;
while (m--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
rev[b].push_back(a);
}
// prepare topological sorting
for (int i = 1; i <= n; i++) dfs(i);
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= n; i++) dfsRev(i);
reverse(all(line)); reverse(all(lineRev));
// read queries and process big ones
for (int i = 0; i < q; i++) {
int v, k; cin >> v >> k;
vector<int> vec(k);
for (int j = 0; j < k; j++) cin >> vec[j];
if (k < srt)
qry[v].push_back(query(i, vec));
else ans[i] = dpCalc(v, vec);
}
// process small queries
for (int u : line) {
process(u);
for (query &it : qry[u]) {
for (int node : it.block) check[node] = 1;
bool ready = 0;
for (pii iter : best[u]) {
if (check[iter.second]) continue;
ans[it.id] = iter.first, ready = 1;
break;
}
if (!ready) ans[it.id] = INT_MIN;
for (int node : it.block) check[node] = 0;
}
}
// print answers
for (int i = 0; i < q; i++) cout << (ans[i] == INT_MIN ? -1 : ans[i]) << "\n";
return 0;
}
Compilation message
bitaro.cpp: In function 'void process(int)':
bitaro.cpp:56:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (iter[v] == best[v].size()) continue;
| ~~~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if (iter[save] == best[save].size()) cnt--;
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
3 ms |
10844 KB |
Output is correct |
4 |
Correct |
3 ms |
11004 KB |
Output is correct |
5 |
Correct |
6 ms |
13404 KB |
Output is correct |
6 |
Correct |
7 ms |
13148 KB |
Output is correct |
7 |
Correct |
8 ms |
13148 KB |
Output is correct |
8 |
Correct |
11 ms |
14940 KB |
Output is correct |
9 |
Correct |
11 ms |
14940 KB |
Output is correct |
10 |
Correct |
10 ms |
14936 KB |
Output is correct |
11 |
Correct |
7 ms |
14936 KB |
Output is correct |
12 |
Correct |
6 ms |
13616 KB |
Output is correct |
13 |
Correct |
9 ms |
14940 KB |
Output is correct |
14 |
Correct |
6 ms |
13148 KB |
Output is correct |
15 |
Correct |
5 ms |
12124 KB |
Output is correct |
16 |
Correct |
7 ms |
12888 KB |
Output is correct |
17 |
Correct |
7 ms |
13916 KB |
Output is correct |
18 |
Correct |
6 ms |
12636 KB |
Output is correct |
19 |
Correct |
9 ms |
14172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
3 ms |
10844 KB |
Output is correct |
4 |
Correct |
3 ms |
11004 KB |
Output is correct |
5 |
Correct |
6 ms |
13404 KB |
Output is correct |
6 |
Correct |
7 ms |
13148 KB |
Output is correct |
7 |
Correct |
8 ms |
13148 KB |
Output is correct |
8 |
Correct |
11 ms |
14940 KB |
Output is correct |
9 |
Correct |
11 ms |
14940 KB |
Output is correct |
10 |
Correct |
10 ms |
14936 KB |
Output is correct |
11 |
Correct |
7 ms |
14936 KB |
Output is correct |
12 |
Correct |
6 ms |
13616 KB |
Output is correct |
13 |
Correct |
9 ms |
14940 KB |
Output is correct |
14 |
Correct |
6 ms |
13148 KB |
Output is correct |
15 |
Correct |
5 ms |
12124 KB |
Output is correct |
16 |
Correct |
7 ms |
12888 KB |
Output is correct |
17 |
Correct |
7 ms |
13916 KB |
Output is correct |
18 |
Correct |
6 ms |
12636 KB |
Output is correct |
19 |
Correct |
9 ms |
14172 KB |
Output is correct |
20 |
Correct |
138 ms |
18932 KB |
Output is correct |
21 |
Correct |
130 ms |
19004 KB |
Output is correct |
22 |
Correct |
151 ms |
19340 KB |
Output is correct |
23 |
Correct |
142 ms |
19036 KB |
Output is correct |
24 |
Correct |
499 ms |
333984 KB |
Output is correct |
25 |
Correct |
475 ms |
333296 KB |
Output is correct |
26 |
Correct |
499 ms |
333608 KB |
Output is correct |
27 |
Correct |
565 ms |
428112 KB |
Output is correct |
28 |
Correct |
568 ms |
428104 KB |
Output is correct |
29 |
Correct |
543 ms |
428088 KB |
Output is correct |
30 |
Correct |
543 ms |
422444 KB |
Output is correct |
31 |
Correct |
556 ms |
412232 KB |
Output is correct |
32 |
Correct |
571 ms |
422520 KB |
Output is correct |
33 |
Correct |
392 ms |
265436 KB |
Output is correct |
34 |
Correct |
338 ms |
218320 KB |
Output is correct |
35 |
Correct |
421 ms |
263504 KB |
Output is correct |
36 |
Correct |
475 ms |
347296 KB |
Output is correct |
37 |
Correct |
511 ms |
319064 KB |
Output is correct |
38 |
Correct |
522 ms |
347728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
2 ms |
10844 KB |
Output is correct |
3 |
Correct |
3 ms |
10844 KB |
Output is correct |
4 |
Correct |
3 ms |
11004 KB |
Output is correct |
5 |
Correct |
6 ms |
13404 KB |
Output is correct |
6 |
Correct |
7 ms |
13148 KB |
Output is correct |
7 |
Correct |
8 ms |
13148 KB |
Output is correct |
8 |
Correct |
11 ms |
14940 KB |
Output is correct |
9 |
Correct |
11 ms |
14940 KB |
Output is correct |
10 |
Correct |
10 ms |
14936 KB |
Output is correct |
11 |
Correct |
7 ms |
14936 KB |
Output is correct |
12 |
Correct |
6 ms |
13616 KB |
Output is correct |
13 |
Correct |
9 ms |
14940 KB |
Output is correct |
14 |
Correct |
6 ms |
13148 KB |
Output is correct |
15 |
Correct |
5 ms |
12124 KB |
Output is correct |
16 |
Correct |
7 ms |
12888 KB |
Output is correct |
17 |
Correct |
7 ms |
13916 KB |
Output is correct |
18 |
Correct |
6 ms |
12636 KB |
Output is correct |
19 |
Correct |
9 ms |
14172 KB |
Output is correct |
20 |
Correct |
138 ms |
18932 KB |
Output is correct |
21 |
Correct |
130 ms |
19004 KB |
Output is correct |
22 |
Correct |
151 ms |
19340 KB |
Output is correct |
23 |
Correct |
142 ms |
19036 KB |
Output is correct |
24 |
Correct |
499 ms |
333984 KB |
Output is correct |
25 |
Correct |
475 ms |
333296 KB |
Output is correct |
26 |
Correct |
499 ms |
333608 KB |
Output is correct |
27 |
Correct |
565 ms |
428112 KB |
Output is correct |
28 |
Correct |
568 ms |
428104 KB |
Output is correct |
29 |
Correct |
543 ms |
428088 KB |
Output is correct |
30 |
Correct |
543 ms |
422444 KB |
Output is correct |
31 |
Correct |
556 ms |
412232 KB |
Output is correct |
32 |
Correct |
571 ms |
422520 KB |
Output is correct |
33 |
Correct |
392 ms |
265436 KB |
Output is correct |
34 |
Correct |
338 ms |
218320 KB |
Output is correct |
35 |
Correct |
421 ms |
263504 KB |
Output is correct |
36 |
Correct |
475 ms |
347296 KB |
Output is correct |
37 |
Correct |
511 ms |
319064 KB |
Output is correct |
38 |
Correct |
522 ms |
347728 KB |
Output is correct |
39 |
Correct |
517 ms |
335012 KB |
Output is correct |
40 |
Correct |
489 ms |
332912 KB |
Output is correct |
41 |
Correct |
477 ms |
332028 KB |
Output is correct |
42 |
Correct |
655 ms |
331344 KB |
Output is correct |
43 |
Correct |
512 ms |
330680 KB |
Output is correct |
44 |
Incorrect |
201 ms |
25940 KB |
Output isn't correct |
45 |
Halted |
0 ms |
0 KB |
- |