# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
100692 | 2019-03-13T11:51:22 Z | JPN20 | Bitaro’s Party (JOI18_bitaro) | C++17 | 2000 ms | 116340 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]; pair<int, int> G[1 << 17][120], I[12000000]; int SZ[1 << 17]; 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 < SZ[pos]; i++) { if (used[G[pos][i].second] == false) { maxn = max(maxn, G[pos][i].first); break; } } 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++) { int cntv = 0, cnts = 0; for (int pos : Y[i]) { for (int k = 0; k < SZ[pos]; k++) { I[cntv] = make_pair(G[pos][k].first + 1, G[pos][k].second); cntv++; } } I[cntv] = make_pair(0, i); cntv++; sort(I, I + cntv, greater<pair<int, int>>()); for (int j = 0; j < cntv; j++) { if (used[I[j].second] == false) { used[I[j].second] = true; G[i][cnts] = I[j]; cnts++; } if (cnts >= BACKET) break; } SZ[i] = cnts; for (int j = 0; j < cntv; j++) used[I[j].second] = false; } } int main(){ //FILE *in = freopen("in1.txt", "r", stdin); //FILE *out = freopen("out1.txt", "w", stdout); 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 | 15 ms | 12672 KB | Output is correct |
2 | Correct | 13 ms | 12672 KB | Output is correct |
3 | Correct | 13 ms | 12672 KB | Output is correct |
4 | Correct | 13 ms | 12672 KB | Output is correct |
5 | Correct | 17 ms | 13696 KB | Output is correct |
6 | Correct | 18 ms | 13696 KB | Output is correct |
7 | Correct | 16 ms | 13696 KB | Output is correct |
8 | Correct | 21 ms | 13696 KB | Output is correct |
9 | Correct | 16 ms | 13696 KB | Output is correct |
10 | Correct | 17 ms | 13756 KB | Output is correct |
11 | Correct | 17 ms | 13696 KB | Output is correct |
12 | Correct | 19 ms | 13732 KB | Output is correct |
13 | Correct | 18 ms | 13696 KB | Output is correct |
14 | Correct | 21 ms | 13696 KB | Output is correct |
15 | Correct | 18 ms | 13696 KB | Output is correct |
16 | Correct | 17 ms | 13696 KB | Output is correct |
17 | Correct | 18 ms | 13696 KB | Output is correct |
18 | Correct | 20 ms | 13696 KB | Output is correct |
19 | Correct | 18 ms | 13696 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 12672 KB | Output is correct |
2 | Correct | 13 ms | 12672 KB | Output is correct |
3 | Correct | 13 ms | 12672 KB | Output is correct |
4 | Correct | 13 ms | 12672 KB | Output is correct |
5 | Correct | 17 ms | 13696 KB | Output is correct |
6 | Correct | 18 ms | 13696 KB | Output is correct |
7 | Correct | 16 ms | 13696 KB | Output is correct |
8 | Correct | 21 ms | 13696 KB | Output is correct |
9 | Correct | 16 ms | 13696 KB | Output is correct |
10 | Correct | 17 ms | 13756 KB | Output is correct |
11 | Correct | 17 ms | 13696 KB | Output is correct |
12 | Correct | 19 ms | 13732 KB | Output is correct |
13 | Correct | 18 ms | 13696 KB | Output is correct |
14 | Correct | 21 ms | 13696 KB | Output is correct |
15 | Correct | 18 ms | 13696 KB | Output is correct |
16 | Correct | 17 ms | 13696 KB | Output is correct |
17 | Correct | 18 ms | 13696 KB | Output is correct |
18 | Correct | 20 ms | 13696 KB | Output is correct |
19 | Correct | 18 ms | 13696 KB | Output is correct |
20 | Correct | 703 ms | 17776 KB | Output is correct |
21 | Correct | 665 ms | 17808 KB | Output is correct |
22 | Correct | 700 ms | 17864 KB | Output is correct |
23 | Correct | 659 ms | 17896 KB | Output is correct |
24 | Correct | 557 ms | 114804 KB | Output is correct |
25 | Correct | 530 ms | 114804 KB | Output is correct |
26 | Correct | 557 ms | 114932 KB | Output is correct |
27 | Correct | 343 ms | 116212 KB | Output is correct |
28 | Correct | 385 ms | 116340 KB | Output is correct |
29 | Correct | 346 ms | 116216 KB | Output is correct |
30 | Correct | 379 ms | 115572 KB | Output is correct |
31 | Correct | 484 ms | 115736 KB | Output is correct |
32 | Correct | 422 ms | 115700 KB | Output is correct |
33 | Correct | 414 ms | 115556 KB | Output is correct |
34 | Correct | 434 ms | 115796 KB | Output is correct |
35 | Correct | 382 ms | 115572 KB | Output is correct |
36 | Correct | 407 ms | 115848 KB | Output is correct |
37 | Correct | 546 ms | 115984 KB | Output is correct |
38 | Correct | 457 ms | 115628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 12672 KB | Output is correct |
2 | Correct | 13 ms | 12672 KB | Output is correct |
3 | Correct | 13 ms | 12672 KB | Output is correct |
4 | Correct | 13 ms | 12672 KB | Output is correct |
5 | Correct | 17 ms | 13696 KB | Output is correct |
6 | Correct | 18 ms | 13696 KB | Output is correct |
7 | Correct | 16 ms | 13696 KB | Output is correct |
8 | Correct | 21 ms | 13696 KB | Output is correct |
9 | Correct | 16 ms | 13696 KB | Output is correct |
10 | Correct | 17 ms | 13756 KB | Output is correct |
11 | Correct | 17 ms | 13696 KB | Output is correct |
12 | Correct | 19 ms | 13732 KB | Output is correct |
13 | Correct | 18 ms | 13696 KB | Output is correct |
14 | Correct | 21 ms | 13696 KB | Output is correct |
15 | Correct | 18 ms | 13696 KB | Output is correct |
16 | Correct | 17 ms | 13696 KB | Output is correct |
17 | Correct | 18 ms | 13696 KB | Output is correct |
18 | Correct | 20 ms | 13696 KB | Output is correct |
19 | Correct | 18 ms | 13696 KB | Output is correct |
20 | Correct | 703 ms | 17776 KB | Output is correct |
21 | Correct | 665 ms | 17808 KB | Output is correct |
22 | Correct | 700 ms | 17864 KB | Output is correct |
23 | Correct | 659 ms | 17896 KB | Output is correct |
24 | Correct | 557 ms | 114804 KB | Output is correct |
25 | Correct | 530 ms | 114804 KB | Output is correct |
26 | Correct | 557 ms | 114932 KB | Output is correct |
27 | Correct | 343 ms | 116212 KB | Output is correct |
28 | Correct | 385 ms | 116340 KB | Output is correct |
29 | Correct | 346 ms | 116216 KB | Output is correct |
30 | Correct | 379 ms | 115572 KB | Output is correct |
31 | Correct | 484 ms | 115736 KB | Output is correct |
32 | Correct | 422 ms | 115700 KB | Output is correct |
33 | Correct | 414 ms | 115556 KB | Output is correct |
34 | Correct | 434 ms | 115796 KB | Output is correct |
35 | Correct | 382 ms | 115572 KB | Output is correct |
36 | Correct | 407 ms | 115848 KB | Output is correct |
37 | Correct | 546 ms | 115984 KB | Output is correct |
38 | Correct | 457 ms | 115628 KB | Output is correct |
39 | Correct | 617 ms | 114156 KB | Output is correct |
40 | Correct | 562 ms | 113920 KB | Output is correct |
41 | Execution timed out | 2057 ms | 114352 KB | Time limit exceeded |
42 | Halted | 0 ms | 0 KB | - |