# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
112482 | 2019-05-20T06:53:12 Z | choikiwon | Bitaro’s Party (JOI18_bitaro) | C++17 | 1312 ms | 220540 KB |
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MN = 100010; const int SQ = 200; int N, M, Q; vector<int> adj[MN], radj[MN]; int chk[MN], used[MN]; vector<pii> mrg(vector<pii> &a, vector<pii> &b) { vector<pii> ret; int pos1 = 0, pos2 = 0; while(ret.size() < SQ && pos1 < a.size() && pos2 < b.size()) { if(used[ a[pos1].second ]) { pos1++; continue; } if(used[ b[pos2].second ]) { pos2++; continue; } if(a[pos1].first > b[pos2].first + 1) { ret.push_back(a[pos1]); used[ a[pos1].second ] = 1; pos1++; } else { ret.push_back(pii(b[pos2].first + 1, b[pos2].second)); used[ b[pos2].second ] = 1; pos2++; } } while(ret.size() < SQ && pos1 < a.size()) { if(used[ a[pos1].second ]) { pos1++; continue; } ret.push_back(a[pos1]); used[ a[pos1].second ] = 1; pos1++; } while(ret.size() < SQ && pos2 < b.size()) { if(used[ b[pos2].second ]) { pos2++; continue; } ret.push_back(pii(b[pos2].first + 1, b[pos2].second)); used[ b[pos2].second ] = 1; pos2++; } for(int i = 0; i < ret.size(); i++) used[ ret[i].second ] = 0; return ret; } vector<pii> dp1[MN]; int dp2[MN]; void solve1() { for(int u = 0; u < N; u++) { dp1[u].push_back({0, u}); for(int i = 0; i < radj[u].size(); i++) { int v = radj[u][i]; dp1[u] = mrg(dp1[u], dp1[v]); } } } void solve2(int x) { dp2[x] = 0; for(int u = x - 1; u >= 0; u--) { dp2[u] = -1e9; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v > x) continue; dp2[u] = max(dp2[u], dp2[v] + 1); } } } int main() { scanf("%d %d %d", &N, &M, &Q); for(int i = 0; i < M; i++) { int u, v; scanf("%d %d", &u, &v); u--; v--; adj[u].push_back(v); radj[v].push_back(u); } solve1(); for(int i = 0; i < Q; i++) { int t, y; scanf("%d %d", &t, &y); t--; vector<int> c(y); for(int j = 0; j < y; j++) { scanf("%d", &c[j]); chk[ --c[j] ] = 1; } if(y >= SQ) { solve2(t); int ans = -1; for(int j = 0; j <= t; j++) if(!chk[j]) ans = max(ans, dp2[j]); printf("%d\n", ans); } else { int ans = -1; for(int j = 0; j < dp1[t].size(); j++) if(!chk[ dp1[t][j].second ]) { ans = dp1[t][j].first; break; } printf("%d\n", ans); } for(int j = 0; j < y; j++) chk[ c[j] ] = 0; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7424 KB | Output is correct |
2 | Correct | 8 ms | 7424 KB | Output is correct |
3 | Correct | 7 ms | 7424 KB | Output is correct |
4 | Correct | 7 ms | 7424 KB | Output is correct |
5 | Correct | 10 ms | 7936 KB | Output is correct |
6 | Correct | 10 ms | 7936 KB | Output is correct |
7 | Correct | 10 ms | 7936 KB | Output is correct |
8 | Correct | 15 ms | 9344 KB | Output is correct |
9 | Correct | 15 ms | 9344 KB | Output is correct |
10 | Correct | 15 ms | 9344 KB | Output is correct |
11 | Correct | 14 ms | 9208 KB | Output is correct |
12 | Correct | 12 ms | 8576 KB | Output is correct |
13 | Correct | 13 ms | 9088 KB | Output is correct |
14 | Correct | 14 ms | 8576 KB | Output is correct |
15 | Correct | 13 ms | 8028 KB | Output is correct |
16 | Correct | 14 ms | 8576 KB | Output is correct |
17 | Correct | 14 ms | 8800 KB | Output is correct |
18 | Correct | 13 ms | 8320 KB | Output is correct |
19 | Correct | 14 ms | 8832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7424 KB | Output is correct |
2 | Correct | 8 ms | 7424 KB | Output is correct |
3 | Correct | 7 ms | 7424 KB | Output is correct |
4 | Correct | 7 ms | 7424 KB | Output is correct |
5 | Correct | 10 ms | 7936 KB | Output is correct |
6 | Correct | 10 ms | 7936 KB | Output is correct |
7 | Correct | 10 ms | 7936 KB | Output is correct |
8 | Correct | 15 ms | 9344 KB | Output is correct |
9 | Correct | 15 ms | 9344 KB | Output is correct |
10 | Correct | 15 ms | 9344 KB | Output is correct |
11 | Correct | 14 ms | 9208 KB | Output is correct |
12 | Correct | 12 ms | 8576 KB | Output is correct |
13 | Correct | 13 ms | 9088 KB | Output is correct |
14 | Correct | 14 ms | 8576 KB | Output is correct |
15 | Correct | 13 ms | 8028 KB | Output is correct |
16 | Correct | 14 ms | 8576 KB | Output is correct |
17 | Correct | 14 ms | 8800 KB | Output is correct |
18 | Correct | 13 ms | 8320 KB | Output is correct |
19 | Correct | 14 ms | 8832 KB | Output is correct |
20 | Correct | 485 ms | 11636 KB | Output is correct |
21 | Correct | 478 ms | 11640 KB | Output is correct |
22 | Correct | 494 ms | 11704 KB | Output is correct |
23 | Correct | 542 ms | 11720 KB | Output is correct |
24 | Correct | 920 ms | 156328 KB | Output is correct |
25 | Correct | 939 ms | 160480 KB | Output is correct |
26 | Correct | 885 ms | 160376 KB | Output is correct |
27 | Correct | 954 ms | 216824 KB | Output is correct |
28 | Correct | 918 ms | 216824 KB | Output is correct |
29 | Correct | 921 ms | 216696 KB | Output is correct |
30 | Correct | 898 ms | 215856 KB | Output is correct |
31 | Correct | 904 ms | 210672 KB | Output is correct |
32 | Correct | 873 ms | 215672 KB | Output is correct |
33 | Correct | 725 ms | 138440 KB | Output is correct |
34 | Correct | 684 ms | 120312 KB | Output is correct |
35 | Correct | 720 ms | 137564 KB | Output is correct |
36 | Correct | 899 ms | 178068 KB | Output is correct |
37 | Correct | 848 ms | 165824 KB | Output is correct |
38 | Correct | 878 ms | 178304 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7424 KB | Output is correct |
2 | Correct | 8 ms | 7424 KB | Output is correct |
3 | Correct | 7 ms | 7424 KB | Output is correct |
4 | Correct | 7 ms | 7424 KB | Output is correct |
5 | Correct | 10 ms | 7936 KB | Output is correct |
6 | Correct | 10 ms | 7936 KB | Output is correct |
7 | Correct | 10 ms | 7936 KB | Output is correct |
8 | Correct | 15 ms | 9344 KB | Output is correct |
9 | Correct | 15 ms | 9344 KB | Output is correct |
10 | Correct | 15 ms | 9344 KB | Output is correct |
11 | Correct | 14 ms | 9208 KB | Output is correct |
12 | Correct | 12 ms | 8576 KB | Output is correct |
13 | Correct | 13 ms | 9088 KB | Output is correct |
14 | Correct | 14 ms | 8576 KB | Output is correct |
15 | Correct | 13 ms | 8028 KB | Output is correct |
16 | Correct | 14 ms | 8576 KB | Output is correct |
17 | Correct | 14 ms | 8800 KB | Output is correct |
18 | Correct | 13 ms | 8320 KB | Output is correct |
19 | Correct | 14 ms | 8832 KB | Output is correct |
20 | Correct | 485 ms | 11636 KB | Output is correct |
21 | Correct | 478 ms | 11640 KB | Output is correct |
22 | Correct | 494 ms | 11704 KB | Output is correct |
23 | Correct | 542 ms | 11720 KB | Output is correct |
24 | Correct | 920 ms | 156328 KB | Output is correct |
25 | Correct | 939 ms | 160480 KB | Output is correct |
26 | Correct | 885 ms | 160376 KB | Output is correct |
27 | Correct | 954 ms | 216824 KB | Output is correct |
28 | Correct | 918 ms | 216824 KB | Output is correct |
29 | Correct | 921 ms | 216696 KB | Output is correct |
30 | Correct | 898 ms | 215856 KB | Output is correct |
31 | Correct | 904 ms | 210672 KB | Output is correct |
32 | Correct | 873 ms | 215672 KB | Output is correct |
33 | Correct | 725 ms | 138440 KB | Output is correct |
34 | Correct | 684 ms | 120312 KB | Output is correct |
35 | Correct | 720 ms | 137564 KB | Output is correct |
36 | Correct | 899 ms | 178068 KB | Output is correct |
37 | Correct | 848 ms | 165824 KB | Output is correct |
38 | Correct | 878 ms | 178304 KB | Output is correct |
39 | Correct | 986 ms | 157328 KB | Output is correct |
40 | Correct | 882 ms | 158316 KB | Output is correct |
41 | Correct | 869 ms | 158800 KB | Output is correct |
42 | Correct | 1064 ms | 159444 KB | Output is correct |
43 | Correct | 901 ms | 157932 KB | Output is correct |
44 | Correct | 523 ms | 12092 KB | Output is correct |
45 | Correct | 492 ms | 11580 KB | Output is correct |
46 | Correct | 490 ms | 11640 KB | Output is correct |
47 | Correct | 518 ms | 11640 KB | Output is correct |
48 | Correct | 481 ms | 11580 KB | Output is correct |
49 | Correct | 978 ms | 216536 KB | Output is correct |
50 | Correct | 920 ms | 215928 KB | Output is correct |
51 | Correct | 511 ms | 12176 KB | Output is correct |
52 | Correct | 485 ms | 11640 KB | Output is correct |
53 | Correct | 924 ms | 177016 KB | Output is correct |
54 | Correct | 931 ms | 165240 KB | Output is correct |
55 | Correct | 875 ms | 176692 KB | Output is correct |
56 | Correct | 896 ms | 165496 KB | Output is correct |
57 | Correct | 532 ms | 11964 KB | Output is correct |
58 | Correct | 539 ms | 11896 KB | Output is correct |
59 | Correct | 520 ms | 11692 KB | Output is correct |
60 | Correct | 506 ms | 11640 KB | Output is correct |
61 | Correct | 1046 ms | 216312 KB | Output is correct |
62 | Correct | 943 ms | 177912 KB | Output is correct |
63 | Correct | 948 ms | 164856 KB | Output is correct |
64 | Correct | 1312 ms | 216184 KB | Output is correct |
65 | Correct | 1155 ms | 177272 KB | Output is correct |
66 | Correct | 1173 ms | 166052 KB | Output is correct |
67 | Correct | 1202 ms | 216284 KB | Output is correct |
68 | Correct | 1124 ms | 180468 KB | Output is correct |
69 | Correct | 1143 ms | 166392 KB | Output is correct |
70 | Correct | 948 ms | 219128 KB | Output is correct |
71 | Correct | 897 ms | 180472 KB | Output is correct |
72 | Correct | 886 ms | 168384 KB | Output is correct |
73 | Correct | 1046 ms | 219216 KB | Output is correct |
74 | Correct | 948 ms | 180680 KB | Output is correct |
75 | Correct | 988 ms | 168016 KB | Output is correct |
76 | Correct | 988 ms | 220540 KB | Output is correct |
77 | Correct | 990 ms | 219684 KB | Output is correct |
78 | Correct | 931 ms | 219560 KB | Output is correct |
79 | Correct | 515 ms | 14456 KB | Output is correct |
80 | Correct | 486 ms | 13540 KB | Output is correct |
81 | Correct | 476 ms | 13020 KB | Output is correct |
82 | Correct | 941 ms | 219640 KB | Output is correct |
83 | Correct | 1002 ms | 214376 KB | Output is correct |
84 | Correct | 1006 ms | 218824 KB | Output is correct |
85 | Correct | 1018 ms | 213440 KB | Output is correct |
86 | Correct | 933 ms | 218744 KB | Output is correct |
87 | Correct | 995 ms | 213752 KB | Output is correct |
88 | Correct | 518 ms | 14492 KB | Output is correct |
89 | Correct | 550 ms | 14480 KB | Output is correct |
90 | Correct | 517 ms | 13572 KB | Output is correct |
91 | Correct | 533 ms | 13496 KB | Output is correct |
92 | Correct | 502 ms | 13184 KB | Output is correct |
93 | Correct | 504 ms | 13176 KB | Output is correct |
94 | Correct | 845 ms | 142580 KB | Output is correct |
95 | Correct | 776 ms | 123180 KB | Output is correct |
96 | Correct | 771 ms | 141048 KB | Output is correct |
97 | Correct | 696 ms | 124508 KB | Output is correct |
98 | Correct | 808 ms | 141432 KB | Output is correct |
99 | Correct | 704 ms | 124204 KB | Output is correct |
100 | Correct | 581 ms | 14528 KB | Output is correct |
101 | Correct | 584 ms | 14456 KB | Output is correct |
102 | Correct | 562 ms | 13688 KB | Output is correct |
103 | Correct | 545 ms | 13516 KB | Output is correct |
104 | Correct | 547 ms | 13176 KB | Output is correct |
105 | Correct | 549 ms | 13176 KB | Output is correct |
106 | Correct | 947 ms | 181196 KB | Output is correct |
107 | Correct | 954 ms | 169436 KB | Output is correct |
108 | Correct | 926 ms | 181368 KB | Output is correct |
109 | Correct | 874 ms | 168204 KB | Output is correct |
110 | Correct | 861 ms | 181684 KB | Output is correct |
111 | Correct | 900 ms | 169072 KB | Output is correct |
112 | Correct | 516 ms | 14608 KB | Output is correct |
113 | Correct | 519 ms | 14520 KB | Output is correct |
114 | Correct | 520 ms | 13516 KB | Output is correct |
115 | Correct | 493 ms | 13516 KB | Output is correct |
116 | Correct | 476 ms | 13380 KB | Output is correct |
117 | Correct | 608 ms | 13188 KB | Output is correct |
118 | Correct | 978 ms | 218676 KB | Output is correct |
119 | Correct | 872 ms | 180216 KB | Output is correct |
120 | Correct | 868 ms | 167356 KB | Output is correct |
121 | Correct | 961 ms | 218428 KB | Output is correct |
122 | Correct | 885 ms | 179584 KB | Output is correct |
123 | Correct | 914 ms | 167092 KB | Output is correct |
124 | Correct | 961 ms | 218584 KB | Output is correct |
125 | Correct | 839 ms | 180576 KB | Output is correct |
126 | Correct | 883 ms | 167024 KB | Output is correct |