#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long
using namespace std;
vector <ll> adj[100000];
priority_queue <array<ll, 2>> pq;
queue <ll> Q;
array <ll, 2> dp[100000][330];
ll n, m, q, a, k, b, f, rt = 330, dist[100000], B[100000], in[100000], visited[100000], ver[100000];
void dfs(ll u) {
visited[u] = q;
in[u] = 0;
for (auto v : adj[u]) {
if (visited[v] != q) dfs(v);
++in[v];
}
}
int main() {
cin >> n >> m >> q;
for (int i=0; i<m; ++i) {
cin >> a >> b;
--a, --b;
adj[b].push_back(a);
}
for (int i=0; i<n; ++i) {
B[i] = visited[i] = ver[i] = -1;
while (!pq.empty()) pq.pop();
pq.push({-1, i});
for (int j=0; j<rt; ++j) {
dp[i][j] = {(ll)-1e18, -1};
}
for (auto u : adj[i]) {
for (int j=0; j<rt; ++j) {
if (dp[u][j][1] == -1) break;
pq.push(dp[u][j]);
}
}
for (int j=0; j<rt; ++j) {
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (ver[u] != i) {
dp[i][j] = {w+1, u};
ver[u] = i;
break;
}
}
}
}
while (q--) {
cin >> a >> k;
--a;
for (int i=0; i<k; ++i) {
cin >> b;
--b;
B[b] = q;
}
if (k < rt) {
for (int i=0; i<rt; ++i) {
if (dp[a][i][1] == -1) {
cout << "-1\n";
break;
}
if (B[dp[a][i][1]] != q) {
cout << dp[a][i][0] << '\n';
break;
}
}
}
else {
dfs(a);
Q.push(a);
dist[a] = 0;
f = -1;
while (!Q.empty()) {
auto u = Q.front();
Q.pop();
if (B[u] != q) f = max(f, dist[u]);
for (auto v : adj[u]) {
--in[v];
dist[v] = max(dist[v], dist[u]+1);
if (!in[v]) Q.push(v);
}
}
cout << f << '\n';
}
}
}
Compilation message
bitaro.cpp: In function 'int main()':
bitaro.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | auto [w, u] = pq.top();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8028 KB |
Output is correct |
2 |
Correct |
2 ms |
8028 KB |
Output is correct |
3 |
Correct |
2 ms |
8096 KB |
Output is correct |
4 |
Correct |
2 ms |
8028 KB |
Output is correct |
5 |
Correct |
7 ms |
14172 KB |
Output is correct |
6 |
Correct |
7 ms |
14172 KB |
Output is correct |
7 |
Correct |
7 ms |
14320 KB |
Output is correct |
8 |
Correct |
33 ms |
14404 KB |
Output is correct |
9 |
Correct |
32 ms |
14388 KB |
Output is correct |
10 |
Correct |
31 ms |
14380 KB |
Output is correct |
11 |
Correct |
30 ms |
14248 KB |
Output is correct |
12 |
Correct |
14 ms |
14168 KB |
Output is correct |
13 |
Correct |
29 ms |
14172 KB |
Output is correct |
14 |
Correct |
30 ms |
14424 KB |
Output is correct |
15 |
Correct |
17 ms |
14684 KB |
Output is correct |
16 |
Correct |
27 ms |
14368 KB |
Output is correct |
17 |
Correct |
31 ms |
14364 KB |
Output is correct |
18 |
Correct |
14 ms |
14684 KB |
Output is correct |
19 |
Correct |
25 ms |
14388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8028 KB |
Output is correct |
2 |
Correct |
2 ms |
8028 KB |
Output is correct |
3 |
Correct |
2 ms |
8096 KB |
Output is correct |
4 |
Correct |
2 ms |
8028 KB |
Output is correct |
5 |
Correct |
7 ms |
14172 KB |
Output is correct |
6 |
Correct |
7 ms |
14172 KB |
Output is correct |
7 |
Correct |
7 ms |
14320 KB |
Output is correct |
8 |
Correct |
33 ms |
14404 KB |
Output is correct |
9 |
Correct |
32 ms |
14388 KB |
Output is correct |
10 |
Correct |
31 ms |
14380 KB |
Output is correct |
11 |
Correct |
30 ms |
14248 KB |
Output is correct |
12 |
Correct |
14 ms |
14168 KB |
Output is correct |
13 |
Correct |
29 ms |
14172 KB |
Output is correct |
14 |
Correct |
30 ms |
14424 KB |
Output is correct |
15 |
Correct |
17 ms |
14684 KB |
Output is correct |
16 |
Correct |
27 ms |
14368 KB |
Output is correct |
17 |
Correct |
31 ms |
14364 KB |
Output is correct |
18 |
Correct |
14 ms |
14684 KB |
Output is correct |
19 |
Correct |
25 ms |
14388 KB |
Output is correct |
20 |
Execution timed out |
2037 ms |
17284 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8028 KB |
Output is correct |
2 |
Correct |
2 ms |
8028 KB |
Output is correct |
3 |
Correct |
2 ms |
8096 KB |
Output is correct |
4 |
Correct |
2 ms |
8028 KB |
Output is correct |
5 |
Correct |
7 ms |
14172 KB |
Output is correct |
6 |
Correct |
7 ms |
14172 KB |
Output is correct |
7 |
Correct |
7 ms |
14320 KB |
Output is correct |
8 |
Correct |
33 ms |
14404 KB |
Output is correct |
9 |
Correct |
32 ms |
14388 KB |
Output is correct |
10 |
Correct |
31 ms |
14380 KB |
Output is correct |
11 |
Correct |
30 ms |
14248 KB |
Output is correct |
12 |
Correct |
14 ms |
14168 KB |
Output is correct |
13 |
Correct |
29 ms |
14172 KB |
Output is correct |
14 |
Correct |
30 ms |
14424 KB |
Output is correct |
15 |
Correct |
17 ms |
14684 KB |
Output is correct |
16 |
Correct |
27 ms |
14368 KB |
Output is correct |
17 |
Correct |
31 ms |
14364 KB |
Output is correct |
18 |
Correct |
14 ms |
14684 KB |
Output is correct |
19 |
Correct |
25 ms |
14388 KB |
Output is correct |
20 |
Execution timed out |
2037 ms |
17284 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |