# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
100687 | 2019-03-13T11:29:11 Z | JPN20 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 131832 KB |
#include <bits/stdc++.h> using namespace std; const int BACKET = 70; 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 | 18816 KB | Output is correct |
2 | Correct | 22 ms | 18816 KB | Output is correct |
3 | Correct | 19 ms | 18816 KB | Output is correct |
4 | Correct | 20 ms | 18808 KB | Output is correct |
5 | Correct | 25 ms | 19328 KB | Output is correct |
6 | Correct | 30 ms | 19324 KB | Output is correct |
7 | Correct | 26 ms | 19328 KB | Output is correct |
8 | Correct | 23 ms | 19840 KB | Output is correct |
9 | Correct | 24 ms | 19840 KB | Output is correct |
10 | Correct | 34 ms | 19836 KB | Output is correct |
11 | Correct | 26 ms | 19840 KB | Output is correct |
12 | Correct | 24 ms | 19832 KB | Output is correct |
13 | Correct | 25 ms | 19840 KB | Output is correct |
14 | Correct | 25 ms | 19456 KB | Output is correct |
15 | Correct | 23 ms | 19320 KB | Output is correct |
16 | Correct | 23 ms | 19584 KB | Output is correct |
17 | Correct | 27 ms | 19584 KB | Output is correct |
18 | Correct | 22 ms | 19456 KB | Output is correct |
19 | Correct | 24 ms | 19712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 18816 KB | Output is correct |
2 | Correct | 22 ms | 18816 KB | Output is correct |
3 | Correct | 19 ms | 18816 KB | Output is correct |
4 | Correct | 20 ms | 18808 KB | Output is correct |
5 | Correct | 25 ms | 19328 KB | Output is correct |
6 | Correct | 30 ms | 19324 KB | Output is correct |
7 | Correct | 26 ms | 19328 KB | Output is correct |
8 | Correct | 23 ms | 19840 KB | Output is correct |
9 | Correct | 24 ms | 19840 KB | Output is correct |
10 | Correct | 34 ms | 19836 KB | Output is correct |
11 | Correct | 26 ms | 19840 KB | Output is correct |
12 | Correct | 24 ms | 19832 KB | Output is correct |
13 | Correct | 25 ms | 19840 KB | Output is correct |
14 | Correct | 25 ms | 19456 KB | Output is correct |
15 | Correct | 23 ms | 19320 KB | Output is correct |
16 | Correct | 23 ms | 19584 KB | Output is correct |
17 | Correct | 27 ms | 19584 KB | Output is correct |
18 | Correct | 22 ms | 19456 KB | Output is correct |
19 | Correct | 24 ms | 19712 KB | Output is correct |
20 | Correct | 1100 ms | 24304 KB | Output is correct |
21 | Correct | 1126 ms | 25680 KB | Output is correct |
22 | Correct | 1182 ms | 25772 KB | Output is correct |
23 | Correct | 1151 ms | 26208 KB | Output is correct |
24 | Correct | 1098 ms | 106172 KB | Output is correct |
25 | Correct | 1004 ms | 107556 KB | Output is correct |
26 | Correct | 1000 ms | 107492 KB | Output is correct |
27 | Correct | 851 ms | 131832 KB | Output is correct |
28 | Correct | 873 ms | 131808 KB | Output is correct |
29 | Correct | 885 ms | 131744 KB | Output is correct |
30 | Correct | 810 ms | 131064 KB | Output is correct |
31 | Correct | 974 ms | 129268 KB | Output is correct |
32 | Correct | 910 ms | 130880 KB | Output is correct |
33 | Correct | 760 ms | 93396 KB | Output is correct |
34 | Correct | 685 ms | 86304 KB | Output is correct |
35 | Correct | 706 ms | 92920 KB | Output is correct |
36 | Correct | 859 ms | 112372 KB | Output is correct |
37 | Correct | 867 ms | 107656 KB | Output is correct |
38 | Correct | 829 ms | 112632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 18816 KB | Output is correct |
2 | Correct | 22 ms | 18816 KB | Output is correct |
3 | Correct | 19 ms | 18816 KB | Output is correct |
4 | Correct | 20 ms | 18808 KB | Output is correct |
5 | Correct | 25 ms | 19328 KB | Output is correct |
6 | Correct | 30 ms | 19324 KB | Output is correct |
7 | Correct | 26 ms | 19328 KB | Output is correct |
8 | Correct | 23 ms | 19840 KB | Output is correct |
9 | Correct | 24 ms | 19840 KB | Output is correct |
10 | Correct | 34 ms | 19836 KB | Output is correct |
11 | Correct | 26 ms | 19840 KB | Output is correct |
12 | Correct | 24 ms | 19832 KB | Output is correct |
13 | Correct | 25 ms | 19840 KB | Output is correct |
14 | Correct | 25 ms | 19456 KB | Output is correct |
15 | Correct | 23 ms | 19320 KB | Output is correct |
16 | Correct | 23 ms | 19584 KB | Output is correct |
17 | Correct | 27 ms | 19584 KB | Output is correct |
18 | Correct | 22 ms | 19456 KB | Output is correct |
19 | Correct | 24 ms | 19712 KB | Output is correct |
20 | Correct | 1100 ms | 24304 KB | Output is correct |
21 | Correct | 1126 ms | 25680 KB | Output is correct |
22 | Correct | 1182 ms | 25772 KB | Output is correct |
23 | Correct | 1151 ms | 26208 KB | Output is correct |
24 | Correct | 1098 ms | 106172 KB | Output is correct |
25 | Correct | 1004 ms | 107556 KB | Output is correct |
26 | Correct | 1000 ms | 107492 KB | Output is correct |
27 | Correct | 851 ms | 131832 KB | Output is correct |
28 | Correct | 873 ms | 131808 KB | Output is correct |
29 | Correct | 885 ms | 131744 KB | Output is correct |
30 | Correct | 810 ms | 131064 KB | Output is correct |
31 | Correct | 974 ms | 129268 KB | Output is correct |
32 | Correct | 910 ms | 130880 KB | Output is correct |
33 | Correct | 760 ms | 93396 KB | Output is correct |
34 | Correct | 685 ms | 86304 KB | Output is correct |
35 | Correct | 706 ms | 92920 KB | Output is correct |
36 | Correct | 859 ms | 112372 KB | Output is correct |
37 | Correct | 867 ms | 107656 KB | Output is correct |
38 | Correct | 829 ms | 112632 KB | Output is correct |
39 | Correct | 1016 ms | 106076 KB | Output is correct |
40 | Correct | 994 ms | 106232 KB | Output is correct |
41 | Execution timed out | 2052 ms | 106844 KB | Time limit exceeded |
42 | Halted | 0 ms | 0 KB | - |