# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
100688 | 2019-03-13T11:30:13 Z | JPN20 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 79848 KB |
#include <bits/stdc++.h> using namespace std; const int BACKET = 50; int N, M, Q, A[1 << 18], B[1 << 18], dp[1 << 18]; vector<int>X[1 << 18], Y[1 << 18]; vector<pair<int, int>> G[1 << 18]; bool used[1 << 18]; int melee_solve(int pos, vector<int>vec) { for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = true; int maxn = -1; for (int i = 0; i < (int)G[pos].size(); i++) { if (used[G[pos][i].second] == false) maxn = max(maxn, G[pos][i].first); } for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = false; return maxn; } int ranged_solve(int pos, vector<int>vec) { for (int i = 1; i <= N; i++) dp[i] = -1; for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = true; for (int i = 1; i <= N; i++) { if (used[i] == false) dp[i] = 0; for (int j = 0; j < (int)Y[i].size(); j++) { if (dp[Y[i][j]] == -1) continue; dp[i] = max(dp[i], dp[Y[i][j]] + 1); } } for (int i = 0; i < (int)vec.size(); i++) used[vec[i]] = false; return dp[pos]; } void init() { for (int i = 1; i <= N; i++) { vector<pair<int, int>>Z; for (int j = 0; j < (int)Y[i].size(); j++) { for (int k = 0; k < (int)G[Y[i][j]].size(); k++) { Z.push_back(make_pair(G[Y[i][j]][k].first + 1, G[Y[i][j]][k].second)); } } Z.push_back(make_pair(0, i)); sort(Z.begin(), Z.end(), greater<pair<int, int>>()); for (int j = 0; j < (int)Z.size(); j++) { if (used[Z[j].second] == false) { used[Z[j].second] = true; G[i].push_back(Z[j]); } if (G[i].size() >= BACKET) break; } for (int j = 0; j < (int)Z.size(); j++) used[Z[j].second] = false; } } int main(){ scanf("%d%d%d", &N, &M, &Q); for (int i = 0; i < M; i++) { scanf("%d%d", &A[i], &B[i]); X[A[i]].push_back(B[i]); Y[B[i]].push_back(A[i]); } init(); for (int i = 1; i <= Q; i++) { int P, S, C; vector<int>vec1; scanf("%d%d", &P, &S); for (int j = 0; j < S; j++) { scanf("%d", &C); vec1.push_back(C); } int ans = 0; if (S < BACKET) ans = melee_solve(P, vec1); else ans = ranged_solve(P, vec1); printf("%d\n", ans); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 18788 KB | Output is correct |
2 | Correct | 20 ms | 18816 KB | Output is correct |
3 | Correct | 22 ms | 18816 KB | Output is correct |
4 | Correct | 17 ms | 18816 KB | Output is correct |
5 | Correct | 25 ms | 19200 KB | Output is correct |
6 | Correct | 23 ms | 19200 KB | Output is correct |
7 | Correct | 31 ms | 19192 KB | Output is correct |
8 | Correct | 31 ms | 19448 KB | Output is correct |
9 | Correct | 26 ms | 19456 KB | Output is correct |
10 | Correct | 27 ms | 19456 KB | Output is correct |
11 | Correct | 28 ms | 19428 KB | Output is correct |
12 | Correct | 28 ms | 19328 KB | Output is correct |
13 | Correct | 26 ms | 19448 KB | Output is correct |
14 | Correct | 25 ms | 19200 KB | Output is correct |
15 | Correct | 24 ms | 19300 KB | Output is correct |
16 | Correct | 21 ms | 19196 KB | Output is correct |
17 | Correct | 22 ms | 19328 KB | Output is correct |
18 | Correct | 22 ms | 19328 KB | Output is correct |
19 | Correct | 22 ms | 19328 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 18788 KB | Output is correct |
2 | Correct | 20 ms | 18816 KB | Output is correct |
3 | Correct | 22 ms | 18816 KB | Output is correct |
4 | Correct | 17 ms | 18816 KB | Output is correct |
5 | Correct | 25 ms | 19200 KB | Output is correct |
6 | Correct | 23 ms | 19200 KB | Output is correct |
7 | Correct | 31 ms | 19192 KB | Output is correct |
8 | Correct | 31 ms | 19448 KB | Output is correct |
9 | Correct | 26 ms | 19456 KB | Output is correct |
10 | Correct | 27 ms | 19456 KB | Output is correct |
11 | Correct | 28 ms | 19428 KB | Output is correct |
12 | Correct | 28 ms | 19328 KB | Output is correct |
13 | Correct | 26 ms | 19448 KB | Output is correct |
14 | Correct | 25 ms | 19200 KB | Output is correct |
15 | Correct | 24 ms | 19300 KB | Output is correct |
16 | Correct | 21 ms | 19196 KB | Output is correct |
17 | Correct | 22 ms | 19328 KB | Output is correct |
18 | Correct | 22 ms | 19328 KB | Output is correct |
19 | Correct | 22 ms | 19328 KB | Output is correct |
20 | Correct | 893 ms | 23552 KB | Output is correct |
21 | Correct | 891 ms | 23652 KB | Output is correct |
22 | Correct | 827 ms | 23452 KB | Output is correct |
23 | Correct | 857 ms | 24076 KB | Output is correct |
24 | Correct | 802 ms | 67804 KB | Output is correct |
25 | Correct | 826 ms | 67960 KB | Output is correct |
26 | Correct | 869 ms | 68220 KB | Output is correct |
27 | Correct | 682 ms | 79848 KB | Output is correct |
28 | Correct | 650 ms | 79732 KB | Output is correct |
29 | Correct | 566 ms | 79692 KB | Output is correct |
30 | Correct | 665 ms | 79092 KB | Output is correct |
31 | Correct | 752 ms | 78492 KB | Output is correct |
32 | Correct | 612 ms | 79092 KB | Output is correct |
33 | Correct | 564 ms | 61532 KB | Output is correct |
34 | Correct | 536 ms | 58676 KB | Output is correct |
35 | Correct | 602 ms | 61172 KB | Output is correct |
36 | Correct | 628 ms | 70124 KB | Output is correct |
37 | Correct | 610 ms | 68112 KB | Output is correct |
38 | Correct | 611 ms | 70164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 18788 KB | Output is correct |
2 | Correct | 20 ms | 18816 KB | Output is correct |
3 | Correct | 22 ms | 18816 KB | Output is correct |
4 | Correct | 17 ms | 18816 KB | Output is correct |
5 | Correct | 25 ms | 19200 KB | Output is correct |
6 | Correct | 23 ms | 19200 KB | Output is correct |
7 | Correct | 31 ms | 19192 KB | Output is correct |
8 | Correct | 31 ms | 19448 KB | Output is correct |
9 | Correct | 26 ms | 19456 KB | Output is correct |
10 | Correct | 27 ms | 19456 KB | Output is correct |
11 | Correct | 28 ms | 19428 KB | Output is correct |
12 | Correct | 28 ms | 19328 KB | Output is correct |
13 | Correct | 26 ms | 19448 KB | Output is correct |
14 | Correct | 25 ms | 19200 KB | Output is correct |
15 | Correct | 24 ms | 19300 KB | Output is correct |
16 | Correct | 21 ms | 19196 KB | Output is correct |
17 | Correct | 22 ms | 19328 KB | Output is correct |
18 | Correct | 22 ms | 19328 KB | Output is correct |
19 | Correct | 22 ms | 19328 KB | Output is correct |
20 | Correct | 893 ms | 23552 KB | Output is correct |
21 | Correct | 891 ms | 23652 KB | Output is correct |
22 | Correct | 827 ms | 23452 KB | Output is correct |
23 | Correct | 857 ms | 24076 KB | Output is correct |
24 | Correct | 802 ms | 67804 KB | Output is correct |
25 | Correct | 826 ms | 67960 KB | Output is correct |
26 | Correct | 869 ms | 68220 KB | Output is correct |
27 | Correct | 682 ms | 79848 KB | Output is correct |
28 | Correct | 650 ms | 79732 KB | Output is correct |
29 | Correct | 566 ms | 79692 KB | Output is correct |
30 | Correct | 665 ms | 79092 KB | Output is correct |
31 | Correct | 752 ms | 78492 KB | Output is correct |
32 | Correct | 612 ms | 79092 KB | Output is correct |
33 | Correct | 564 ms | 61532 KB | Output is correct |
34 | Correct | 536 ms | 58676 KB | Output is correct |
35 | Correct | 602 ms | 61172 KB | Output is correct |
36 | Correct | 628 ms | 70124 KB | Output is correct |
37 | Correct | 610 ms | 68112 KB | Output is correct |
38 | Correct | 611 ms | 70164 KB | Output is correct |
39 | Correct | 874 ms | 67272 KB | Output is correct |
40 | Correct | 862 ms | 67236 KB | Output is correct |
41 | Execution timed out | 2063 ms | 67576 KB | Time limit exceeded |
42 | Halted | 0 ms | 0 KB | - |