# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
199959 | 2020-02-04T11:48:08 Z | dennisstar | Bitaro’s Party (JOI18_bitaro) | C++17 | 1982 ms | 335796 KB |
#include <bits/stdc++.h> #define fi first #define se second #define em emplace #define eb emplace_back #define all(V) (V).begin(), (V).end() using namespace std; typedef vector<int> vim; typedef pair<int, int> pii; const int MAX=400; int N, M, Q, ans[100010], chk[100010], ar[100010]; vim adj[100010], qu[100010], C[100010]; vector<pii> B[100010]; int main() { scanf("%d %d %d", &N, &M, &Q); for (int i=0, u, v; i<M; i++) scanf("%d %d", &u, &v), adj[v].eb(u); for (int i=1, t, y; i<=Q; i++) { scanf("%d %d", &t, &y); qu[t].eb(i); C[i].resize(y); for (auto &j:C[i]) scanf("%d", &j); } for (int i=1; i<=N; i++) { B[i].eb(0, i); for (auto &j:adj[i]) { vector<pii> im; int b=0; for (auto &k:B[i]) { while (b<B[j].size()&&k.fi<B[j][b].fi+1&&im.size()<MAX) { if (!chk[B[j][b].se]) im.eb(B[j][b].fi+1, B[j][b].se), chk[B[j][b].se]=1; b++; } if (im.size()>=MAX) break; if (!chk[k.se]) im.eb(k), chk[k.se]=1; } for (auto &k:im) chk[k.se]=0; B[i]=im; } for (auto &j:qu[i]) { ans[j]=-1; for (auto &k:C[j]) chk[k]=1; if (B[i].size()<MAX||C[j].size()<MAX) { for (auto &k:B[i]) if (!chk[k.se]) { ans[j]=k.fi; break; } } else { for (int k=1; k<=i; k++) { ar[k]=(chk[k]?-1e6:0); for (auto &l:adj[k]) ar[k]=max(ar[k], ar[l]+1); } if (ar[i]>=0) ans[j]=ar[i]; } for (auto &k:C[j]) chk[k]=0; } } for (int i=1; i<=Q; i++) printf("%d\n", ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9720 KB | Output is correct |
2 | Correct | 12 ms | 9720 KB | Output is correct |
3 | Correct | 10 ms | 9720 KB | Output is correct |
4 | Correct | 10 ms | 9592 KB | Output is correct |
5 | Correct | 14 ms | 10104 KB | Output is correct |
6 | Correct | 14 ms | 10104 KB | Output is correct |
7 | Correct | 14 ms | 10104 KB | Output is correct |
8 | Correct | 25 ms | 12280 KB | Output is correct |
9 | Correct | 25 ms | 12284 KB | Output is correct |
10 | Correct | 25 ms | 12280 KB | Output is correct |
11 | Correct | 24 ms | 12024 KB | Output is correct |
12 | Correct | 17 ms | 10744 KB | Output is correct |
13 | Correct | 24 ms | 11896 KB | Output is correct |
14 | Correct | 22 ms | 11264 KB | Output is correct |
15 | Correct | 17 ms | 10488 KB | Output is correct |
16 | Correct | 23 ms | 11256 KB | Output is correct |
17 | Correct | 21 ms | 11384 KB | Output is correct |
18 | Correct | 17 ms | 10616 KB | Output is correct |
19 | Correct | 22 ms | 11384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9720 KB | Output is correct |
2 | Correct | 12 ms | 9720 KB | Output is correct |
3 | Correct | 10 ms | 9720 KB | Output is correct |
4 | Correct | 10 ms | 9592 KB | Output is correct |
5 | Correct | 14 ms | 10104 KB | Output is correct |
6 | Correct | 14 ms | 10104 KB | Output is correct |
7 | Correct | 14 ms | 10104 KB | Output is correct |
8 | Correct | 25 ms | 12280 KB | Output is correct |
9 | Correct | 25 ms | 12284 KB | Output is correct |
10 | Correct | 25 ms | 12280 KB | Output is correct |
11 | Correct | 24 ms | 12024 KB | Output is correct |
12 | Correct | 17 ms | 10744 KB | Output is correct |
13 | Correct | 24 ms | 11896 KB | Output is correct |
14 | Correct | 22 ms | 11264 KB | Output is correct |
15 | Correct | 17 ms | 10488 KB | Output is correct |
16 | Correct | 23 ms | 11256 KB | Output is correct |
17 | Correct | 21 ms | 11384 KB | Output is correct |
18 | Correct | 17 ms | 10616 KB | Output is correct |
19 | Correct | 22 ms | 11384 KB | Output is correct |
20 | Correct | 1192 ms | 13664 KB | Output is correct |
21 | Correct | 981 ms | 13568 KB | Output is correct |
22 | Correct | 1163 ms | 13640 KB | Output is correct |
23 | Correct | 1190 ms | 13820 KB | Output is correct |
24 | Correct | 1383 ms | 192708 KB | Output is correct |
25 | Correct | 1462 ms | 202488 KB | Output is correct |
26 | Correct | 1441 ms | 201976 KB | Output is correct |
27 | Correct | 1830 ms | 328056 KB | Output is correct |
28 | Correct | 1796 ms | 327928 KB | Output is correct |
29 | Correct | 1809 ms | 327776 KB | Output is correct |
30 | Correct | 1805 ms | 327416 KB | Output is correct |
31 | Correct | 1841 ms | 315512 KB | Output is correct |
32 | Correct | 1820 ms | 327160 KB | Output is correct |
33 | Correct | 1381 ms | 204024 KB | Output is correct |
34 | Correct | 1246 ms | 166740 KB | Output is correct |
35 | Correct | 1371 ms | 202608 KB | Output is correct |
36 | Correct | 1633 ms | 265884 KB | Output is correct |
37 | Correct | 1533 ms | 239736 KB | Output is correct |
38 | Correct | 1674 ms | 266244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9720 KB | Output is correct |
2 | Correct | 12 ms | 9720 KB | Output is correct |
3 | Correct | 10 ms | 9720 KB | Output is correct |
4 | Correct | 10 ms | 9592 KB | Output is correct |
5 | Correct | 14 ms | 10104 KB | Output is correct |
6 | Correct | 14 ms | 10104 KB | Output is correct |
7 | Correct | 14 ms | 10104 KB | Output is correct |
8 | Correct | 25 ms | 12280 KB | Output is correct |
9 | Correct | 25 ms | 12284 KB | Output is correct |
10 | Correct | 25 ms | 12280 KB | Output is correct |
11 | Correct | 24 ms | 12024 KB | Output is correct |
12 | Correct | 17 ms | 10744 KB | Output is correct |
13 | Correct | 24 ms | 11896 KB | Output is correct |
14 | Correct | 22 ms | 11264 KB | Output is correct |
15 | Correct | 17 ms | 10488 KB | Output is correct |
16 | Correct | 23 ms | 11256 KB | Output is correct |
17 | Correct | 21 ms | 11384 KB | Output is correct |
18 | Correct | 17 ms | 10616 KB | Output is correct |
19 | Correct | 22 ms | 11384 KB | Output is correct |
20 | Correct | 1192 ms | 13664 KB | Output is correct |
21 | Correct | 981 ms | 13568 KB | Output is correct |
22 | Correct | 1163 ms | 13640 KB | Output is correct |
23 | Correct | 1190 ms | 13820 KB | Output is correct |
24 | Correct | 1383 ms | 192708 KB | Output is correct |
25 | Correct | 1462 ms | 202488 KB | Output is correct |
26 | Correct | 1441 ms | 201976 KB | Output is correct |
27 | Correct | 1830 ms | 328056 KB | Output is correct |
28 | Correct | 1796 ms | 327928 KB | Output is correct |
29 | Correct | 1809 ms | 327776 KB | Output is correct |
30 | Correct | 1805 ms | 327416 KB | Output is correct |
31 | Correct | 1841 ms | 315512 KB | Output is correct |
32 | Correct | 1820 ms | 327160 KB | Output is correct |
33 | Correct | 1381 ms | 204024 KB | Output is correct |
34 | Correct | 1246 ms | 166740 KB | Output is correct |
35 | Correct | 1371 ms | 202608 KB | Output is correct |
36 | Correct | 1633 ms | 265884 KB | Output is correct |
37 | Correct | 1533 ms | 239736 KB | Output is correct |
38 | Correct | 1674 ms | 266244 KB | Output is correct |
39 | Correct | 1520 ms | 200312 KB | Output is correct |
40 | Correct | 1444 ms | 201080 KB | Output is correct |
41 | Correct | 1427 ms | 202488 KB | Output is correct |
42 | Correct | 1500 ms | 201392 KB | Output is correct |
43 | Correct | 1418 ms | 200700 KB | Output is correct |
44 | Correct | 1268 ms | 19576 KB | Output is correct |
45 | Correct | 1229 ms | 16248 KB | Output is correct |
46 | Correct | 1188 ms | 15992 KB | Output is correct |
47 | Correct | 1186 ms | 15564 KB | Output is correct |
48 | Correct | 1173 ms | 15224 KB | Output is correct |
49 | Correct | 1982 ms | 335304 KB | Output is correct |
50 | Correct | 1856 ms | 329956 KB | Output is correct |
51 | Correct | 1086 ms | 18888 KB | Output is correct |
52 | Correct | 1020 ms | 15652 KB | Output is correct |
53 | Correct | 1735 ms | 272188 KB | Output is correct |
54 | Correct | 1644 ms | 247756 KB | Output is correct |
55 | Correct | 1720 ms | 267480 KB | Output is correct |
56 | Correct | 1567 ms | 243184 KB | Output is correct |
57 | Correct | 1219 ms | 19152 KB | Output is correct |
58 | Correct | 1292 ms | 19140 KB | Output is correct |
59 | Correct | 1169 ms | 15920 KB | Output is correct |
60 | Correct | 1205 ms | 15992 KB | Output is correct |
61 | Correct | 1958 ms | 330488 KB | Output is correct |
62 | Correct | 1748 ms | 268916 KB | Output is correct |
63 | Correct | 1664 ms | 242552 KB | Output is correct |
64 | Correct | 1807 ms | 330100 KB | Output is correct |
65 | Correct | 1673 ms | 267460 KB | Output is correct |
66 | Correct | 1582 ms | 243152 KB | Output is correct |
67 | Correct | 1828 ms | 329992 KB | Output is correct |
68 | Correct | 1671 ms | 268560 KB | Output is correct |
69 | Correct | 1558 ms | 240196 KB | Output is correct |
70 | Correct | 1853 ms | 330536 KB | Output is correct |
71 | Correct | 1694 ms | 268948 KB | Output is correct |
72 | Correct | 1590 ms | 243416 KB | Output is correct |
73 | Correct | 1877 ms | 330584 KB | Output is correct |
74 | Correct | 1715 ms | 269084 KB | Output is correct |
75 | Correct | 1607 ms | 243624 KB | Output is correct |
76 | Correct | 1884 ms | 335796 KB | Output is correct |
77 | Correct | 1908 ms | 330616 KB | Output is correct |
78 | Correct | 1874 ms | 331272 KB | Output is correct |
79 | Correct | 1054 ms | 18848 KB | Output is correct |
80 | Correct | 1018 ms | 15608 KB | Output is correct |
81 | Correct | 991 ms | 15084 KB | Output is correct |
82 | Correct | 1907 ms | 335408 KB | Output is correct |
83 | Correct | 1967 ms | 323432 KB | Output is correct |
84 | Correct | 1835 ms | 330336 KB | Output is correct |
85 | Correct | 1853 ms | 318184 KB | Output is correct |
86 | Correct | 1918 ms | 330540 KB | Output is correct |
87 | Correct | 1910 ms | 319184 KB | Output is correct |
88 | Correct | 1281 ms | 19192 KB | Output is correct |
89 | Correct | 1336 ms | 19316 KB | Output is correct |
90 | Correct | 1208 ms | 15836 KB | Output is correct |
91 | Correct | 1232 ms | 15980 KB | Output is correct |
92 | Correct | 1231 ms | 15352 KB | Output is correct |
93 | Correct | 1197 ms | 15256 KB | Output is correct |
94 | Correct | 1512 ms | 212116 KB | Output is correct |
95 | Correct | 1403 ms | 173628 KB | Output is correct |
96 | Correct | 1453 ms | 206268 KB | Output is correct |
97 | Correct | 1299 ms | 172260 KB | Output is correct |
98 | Correct | 1473 ms | 207232 KB | Output is correct |
99 | Correct | 1296 ms | 171768 KB | Output is correct |
100 | Correct | 1317 ms | 19360 KB | Output is correct |
101 | Correct | 1270 ms | 19072 KB | Output is correct |
102 | Correct | 1324 ms | 16092 KB | Output is correct |
103 | Correct | 1305 ms | 15912 KB | Output is correct |
104 | Correct | 1353 ms | 15104 KB | Output is correct |
105 | Correct | 1254 ms | 15232 KB | Output is correct |
106 | Correct | 1816 ms | 272776 KB | Output is correct |
107 | Correct | 1689 ms | 247832 KB | Output is correct |
108 | Correct | 1663 ms | 269476 KB | Output is correct |
109 | Correct | 1566 ms | 242764 KB | Output is correct |
110 | Correct | 1685 ms | 269932 KB | Output is correct |
111 | Correct | 1590 ms | 243960 KB | Output is correct |
112 | Correct | 1249 ms | 19192 KB | Output is correct |
113 | Correct | 1277 ms | 19224 KB | Output is correct |
114 | Correct | 1136 ms | 15864 KB | Output is correct |
115 | Correct | 1191 ms | 15800 KB | Output is correct |
116 | Correct | 1180 ms | 15248 KB | Output is correct |
117 | Correct | 1203 ms | 15224 KB | Output is correct |
118 | Correct | 1835 ms | 330380 KB | Output is correct |
119 | Correct | 1677 ms | 269556 KB | Output is correct |
120 | Correct | 1583 ms | 242620 KB | Output is correct |
121 | Correct | 1810 ms | 330508 KB | Output is correct |
122 | Correct | 1694 ms | 268712 KB | Output is correct |
123 | Correct | 1611 ms | 243144 KB | Output is correct |
124 | Correct | 1814 ms | 330044 KB | Output is correct |
125 | Correct | 1672 ms | 269396 KB | Output is correct |
126 | Correct | 1583 ms | 241876 KB | Output is correct |