# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
100683 | 2019-03-13T11:24:17 Z | JPN20 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 17228 KB |
#include <bits/stdc++.h> using namespace std; const int BACKET = 300; int N, M, Q, A[1 << 17], B[1 << 17], dp[1 << 17]; vector<int>X[1 << 17], Y[1 << 17]; vector<pair<int, int>> G[1 << 17]; bool used[1 << 17]; 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 | 10 ms | 9600 KB | Output is correct |
2 | Correct | 11 ms | 9600 KB | Output is correct |
3 | Correct | 11 ms | 9600 KB | Output is correct |
4 | Correct | 11 ms | 9600 KB | Output is correct |
5 | Correct | 16 ms | 10112 KB | Output is correct |
6 | Correct | 14 ms | 10112 KB | Output is correct |
7 | Correct | 20 ms | 10112 KB | Output is correct |
8 | Correct | 35 ms | 13056 KB | Output is correct |
9 | Correct | 36 ms | 13048 KB | Output is correct |
10 | Correct | 32 ms | 13056 KB | Output is correct |
11 | Correct | 38 ms | 12664 KB | Output is correct |
12 | Correct | 22 ms | 10972 KB | Output is correct |
13 | Correct | 31 ms | 12408 KB | Output is correct |
14 | Correct | 32 ms | 11640 KB | Output is correct |
15 | Correct | 21 ms | 10880 KB | Output is correct |
16 | Correct | 29 ms | 11640 KB | Output is correct |
17 | Correct | 29 ms | 11896 KB | Output is correct |
18 | Correct | 22 ms | 11000 KB | Output is correct |
19 | Correct | 36 ms | 11896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9600 KB | Output is correct |
2 | Correct | 11 ms | 9600 KB | Output is correct |
3 | Correct | 11 ms | 9600 KB | Output is correct |
4 | Correct | 11 ms | 9600 KB | Output is correct |
5 | Correct | 16 ms | 10112 KB | Output is correct |
6 | Correct | 14 ms | 10112 KB | Output is correct |
7 | Correct | 20 ms | 10112 KB | Output is correct |
8 | Correct | 35 ms | 13056 KB | Output is correct |
9 | Correct | 36 ms | 13048 KB | Output is correct |
10 | Correct | 32 ms | 13056 KB | Output is correct |
11 | Correct | 38 ms | 12664 KB | Output is correct |
12 | Correct | 22 ms | 10972 KB | Output is correct |
13 | Correct | 31 ms | 12408 KB | Output is correct |
14 | Correct | 32 ms | 11640 KB | Output is correct |
15 | Correct | 21 ms | 10880 KB | Output is correct |
16 | Correct | 29 ms | 11640 KB | Output is correct |
17 | Correct | 29 ms | 11896 KB | Output is correct |
18 | Correct | 22 ms | 11000 KB | Output is correct |
19 | Correct | 36 ms | 11896 KB | Output is correct |
20 | Execution timed out | 2048 ms | 17228 KB | Time limit exceeded |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9600 KB | Output is correct |
2 | Correct | 11 ms | 9600 KB | Output is correct |
3 | Correct | 11 ms | 9600 KB | Output is correct |
4 | Correct | 11 ms | 9600 KB | Output is correct |
5 | Correct | 16 ms | 10112 KB | Output is correct |
6 | Correct | 14 ms | 10112 KB | Output is correct |
7 | Correct | 20 ms | 10112 KB | Output is correct |
8 | Correct | 35 ms | 13056 KB | Output is correct |
9 | Correct | 36 ms | 13048 KB | Output is correct |
10 | Correct | 32 ms | 13056 KB | Output is correct |
11 | Correct | 38 ms | 12664 KB | Output is correct |
12 | Correct | 22 ms | 10972 KB | Output is correct |
13 | Correct | 31 ms | 12408 KB | Output is correct |
14 | Correct | 32 ms | 11640 KB | Output is correct |
15 | Correct | 21 ms | 10880 KB | Output is correct |
16 | Correct | 29 ms | 11640 KB | Output is correct |
17 | Correct | 29 ms | 11896 KB | Output is correct |
18 | Correct | 22 ms | 11000 KB | Output is correct |
19 | Correct | 36 ms | 11896 KB | Output is correct |
20 | Execution timed out | 2048 ms | 17228 KB | Time limit exceeded |
21 | Halted | 0 ms | 0 KB | - |