# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
46353 | 2018-04-19T17:35:27 Z | SpaimaCarpatilor | Bitaro’s Party (JOI18_bitaro) | C++17 | 1576 ms | 173032 KB |
#include<bits/stdc++.h> using namespace std; const int K = 200; int N, M, Q, maxD[100009], ap[100009], h[100009]; vector < int > v[100009], g[100009]; pair < int, int > *dp[100009]; bool cmp (int i, int j) {return (maxD[i] > maxD[j]);} int main () { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); scanf ("%d %d %d", &N, &M, &Q); while (M --) { int x, y; scanf ("%d %d", &x, &y); v[y].push_back (x); g[x].push_back (y); } for (int i=1; i<=N; i++) { dp[i] = new pair < int, int > [K]; for (int j=0; j<K; j++) dp[i][j] = {-3 * N, 0}; } for (int i=1; i<=N; i++) { int nr = 0; for (auto it : v[i]) for (int j=0; j<K; j++) if (dp[it][j].first >= 0) { int nod = dp[it][j].second; if (ap[nod] == 0 || dp[it][j].first + 1 > maxD[nod]) maxD[nod] = dp[it][j].first + 1; if (ap[nod] == 0) ap[nod] = 1, h[++nr] = nod; } h[++nr] = i, maxD[i] = 0; sort (h + 1, h + nr + 1, cmp); for (int j=1; j<=nr && j<=K; j++) dp[i][j - 1] = {maxD[h[j]], h[j]}; for (int j=nr + 1; j<=K; j++) dp[i][j - 1] = {-1, 0}; for (int j=1; j<=nr; j++) ap[h[j]] = 0; } while (Q --) { int pos, L; scanf ("%d %d", &pos, &L); for (int i=1; i<=L; i++) scanf ("%d", &h[i]), ap[h[i]] = 1; int val = -2; for (int j=0; j<K; j++) { if (dp[pos][j].first < 0) { val = -1; break; } int nod = dp[pos][j].second; if (ap[nod] == 0) { val = dp[pos][j].first; break; } } if (val == -2) { ///that's few times maxD[pos] = 0, val = (ap[pos] ? -1 : 0); for (int i=pos - 1; i>=1; i--) { maxD[i] = -3 * N; for (auto it : g[i]) if (it <= pos && maxD[it] + 1 > maxD[i]) maxD[i] = maxD[it] + 1; if (ap[i] == 0 && maxD[i] > val) val = maxD[i]; } printf ("%d\n", val); for (int i=1; i<=L; i++) ap[h[i]] = 0; continue; } for (int i=1; i<=L; i++) ap[h[i]] = 0; printf ("%d\n", val); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5236 KB | Output is correct |
3 | Correct | 9 ms | 5236 KB | Output is correct |
4 | Correct | 7 ms | 5236 KB | Output is correct |
5 | Correct | 11 ms | 6892 KB | Output is correct |
6 | Correct | 11 ms | 6892 KB | Output is correct |
7 | Correct | 13 ms | 6892 KB | Output is correct |
8 | Correct | 16 ms | 6892 KB | Output is correct |
9 | Correct | 17 ms | 6892 KB | Output is correct |
10 | Correct | 15 ms | 6912 KB | Output is correct |
11 | Correct | 15 ms | 6912 KB | Output is correct |
12 | Correct | 11 ms | 6912 KB | Output is correct |
13 | Correct | 16 ms | 6912 KB | Output is correct |
14 | Correct | 15 ms | 6988 KB | Output is correct |
15 | Correct | 11 ms | 6988 KB | Output is correct |
16 | Correct | 8 ms | 6988 KB | Output is correct |
17 | Correct | 15 ms | 6988 KB | Output is correct |
18 | Correct | 14 ms | 6988 KB | Output is correct |
19 | Correct | 15 ms | 6988 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5236 KB | Output is correct |
3 | Correct | 9 ms | 5236 KB | Output is correct |
4 | Correct | 7 ms | 5236 KB | Output is correct |
5 | Correct | 11 ms | 6892 KB | Output is correct |
6 | Correct | 11 ms | 6892 KB | Output is correct |
7 | Correct | 13 ms | 6892 KB | Output is correct |
8 | Correct | 16 ms | 6892 KB | Output is correct |
9 | Correct | 17 ms | 6892 KB | Output is correct |
10 | Correct | 15 ms | 6912 KB | Output is correct |
11 | Correct | 15 ms | 6912 KB | Output is correct |
12 | Correct | 11 ms | 6912 KB | Output is correct |
13 | Correct | 16 ms | 6912 KB | Output is correct |
14 | Correct | 15 ms | 6988 KB | Output is correct |
15 | Correct | 11 ms | 6988 KB | Output is correct |
16 | Correct | 8 ms | 6988 KB | Output is correct |
17 | Correct | 15 ms | 6988 KB | Output is correct |
18 | Correct | 14 ms | 6988 KB | Output is correct |
19 | Correct | 15 ms | 6988 KB | Output is correct |
20 | Correct | 124 ms | 9192 KB | Output is correct |
21 | Correct | 133 ms | 9324 KB | Output is correct |
22 | Correct | 126 ms | 9348 KB | Output is correct |
23 | Correct | 137 ms | 9348 KB | Output is correct |
24 | Correct | 1309 ms | 170424 KB | Output is correct |
25 | Correct | 1274 ms | 170424 KB | Output is correct |
26 | Correct | 1316 ms | 170424 KB | Output is correct |
27 | Correct | 1045 ms | 171924 KB | Output is correct |
28 | Correct | 1008 ms | 171924 KB | Output is correct |
29 | Correct | 990 ms | 171924 KB | Output is correct |
30 | Correct | 927 ms | 171924 KB | Output is correct |
31 | Correct | 1061 ms | 171924 KB | Output is correct |
32 | Correct | 876 ms | 171924 KB | Output is correct |
33 | Correct | 884 ms | 171924 KB | Output is correct |
34 | Correct | 1166 ms | 171924 KB | Output is correct |
35 | Correct | 911 ms | 171924 KB | Output is correct |
36 | Correct | 968 ms | 171924 KB | Output is correct |
37 | Correct | 1214 ms | 171924 KB | Output is correct |
38 | Correct | 1043 ms | 171924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5236 KB | Output is correct |
3 | Correct | 9 ms | 5236 KB | Output is correct |
4 | Correct | 7 ms | 5236 KB | Output is correct |
5 | Correct | 11 ms | 6892 KB | Output is correct |
6 | Correct | 11 ms | 6892 KB | Output is correct |
7 | Correct | 13 ms | 6892 KB | Output is correct |
8 | Correct | 16 ms | 6892 KB | Output is correct |
9 | Correct | 17 ms | 6892 KB | Output is correct |
10 | Correct | 15 ms | 6912 KB | Output is correct |
11 | Correct | 15 ms | 6912 KB | Output is correct |
12 | Correct | 11 ms | 6912 KB | Output is correct |
13 | Correct | 16 ms | 6912 KB | Output is correct |
14 | Correct | 15 ms | 6988 KB | Output is correct |
15 | Correct | 11 ms | 6988 KB | Output is correct |
16 | Correct | 8 ms | 6988 KB | Output is correct |
17 | Correct | 15 ms | 6988 KB | Output is correct |
18 | Correct | 14 ms | 6988 KB | Output is correct |
19 | Correct | 15 ms | 6988 KB | Output is correct |
20 | Correct | 124 ms | 9192 KB | Output is correct |
21 | Correct | 133 ms | 9324 KB | Output is correct |
22 | Correct | 126 ms | 9348 KB | Output is correct |
23 | Correct | 137 ms | 9348 KB | Output is correct |
24 | Correct | 1309 ms | 170424 KB | Output is correct |
25 | Correct | 1274 ms | 170424 KB | Output is correct |
26 | Correct | 1316 ms | 170424 KB | Output is correct |
27 | Correct | 1045 ms | 171924 KB | Output is correct |
28 | Correct | 1008 ms | 171924 KB | Output is correct |
29 | Correct | 990 ms | 171924 KB | Output is correct |
30 | Correct | 927 ms | 171924 KB | Output is correct |
31 | Correct | 1061 ms | 171924 KB | Output is correct |
32 | Correct | 876 ms | 171924 KB | Output is correct |
33 | Correct | 884 ms | 171924 KB | Output is correct |
34 | Correct | 1166 ms | 171924 KB | Output is correct |
35 | Correct | 911 ms | 171924 KB | Output is correct |
36 | Correct | 968 ms | 171924 KB | Output is correct |
37 | Correct | 1214 ms | 171924 KB | Output is correct |
38 | Correct | 1043 ms | 171924 KB | Output is correct |
39 | Correct | 1247 ms | 171924 KB | Output is correct |
40 | Correct | 1264 ms | 171924 KB | Output is correct |
41 | Correct | 1211 ms | 171924 KB | Output is correct |
42 | Correct | 1224 ms | 171924 KB | Output is correct |
43 | Correct | 1179 ms | 171924 KB | Output is correct |
44 | Correct | 181 ms | 171924 KB | Output is correct |
45 | Correct | 272 ms | 171924 KB | Output is correct |
46 | Correct | 146 ms | 171924 KB | Output is correct |
47 | Correct | 132 ms | 171924 KB | Output is correct |
48 | Correct | 120 ms | 171924 KB | Output is correct |
49 | Correct | 1016 ms | 172320 KB | Output is correct |
50 | Correct | 936 ms | 172320 KB | Output is correct |
51 | Correct | 181 ms | 172320 KB | Output is correct |
52 | Correct | 135 ms | 172320 KB | Output is correct |
53 | Correct | 962 ms | 172320 KB | Output is correct |
54 | Correct | 1218 ms | 172320 KB | Output is correct |
55 | Correct | 949 ms | 172320 KB | Output is correct |
56 | Correct | 1165 ms | 172320 KB | Output is correct |
57 | Correct | 161 ms | 172320 KB | Output is correct |
58 | Correct | 171 ms | 172320 KB | Output is correct |
59 | Correct | 151 ms | 172320 KB | Output is correct |
60 | Correct | 132 ms | 172320 KB | Output is correct |
61 | Correct | 1186 ms | 172320 KB | Output is correct |
62 | Correct | 1105 ms | 172320 KB | Output is correct |
63 | Correct | 1374 ms | 172320 KB | Output is correct |
64 | Correct | 1576 ms | 172320 KB | Output is correct |
65 | Correct | 1223 ms | 172320 KB | Output is correct |
66 | Correct | 1218 ms | 172320 KB | Output is correct |
67 | Correct | 1347 ms | 172536 KB | Output is correct |
68 | Correct | 1124 ms | 172536 KB | Output is correct |
69 | Correct | 1120 ms | 172536 KB | Output is correct |
70 | Correct | 1057 ms | 172536 KB | Output is correct |
71 | Correct | 964 ms | 172536 KB | Output is correct |
72 | Correct | 1103 ms | 172536 KB | Output is correct |
73 | Correct | 984 ms | 172536 KB | Output is correct |
74 | Correct | 946 ms | 172536 KB | Output is correct |
75 | Correct | 1067 ms | 172536 KB | Output is correct |
76 | Correct | 1105 ms | 173032 KB | Output is correct |
77 | Correct | 1060 ms | 173032 KB | Output is correct |
78 | Correct | 1093 ms | 173032 KB | Output is correct |
79 | Correct | 162 ms | 173032 KB | Output is correct |
80 | Correct | 134 ms | 173032 KB | Output is correct |
81 | Correct | 119 ms | 173032 KB | Output is correct |
82 | Correct | 1104 ms | 173032 KB | Output is correct |
83 | Correct | 1213 ms | 173032 KB | Output is correct |
84 | Correct | 875 ms | 173032 KB | Output is correct |
85 | Correct | 1109 ms | 173032 KB | Output is correct |
86 | Correct | 871 ms | 173032 KB | Output is correct |
87 | Correct | 1199 ms | 173032 KB | Output is correct |
88 | Correct | 166 ms | 173032 KB | Output is correct |
89 | Correct | 170 ms | 173032 KB | Output is correct |
90 | Correct | 132 ms | 173032 KB | Output is correct |
91 | Correct | 132 ms | 173032 KB | Output is correct |
92 | Correct | 120 ms | 173032 KB | Output is correct |
93 | Correct | 124 ms | 173032 KB | Output is correct |
94 | Correct | 919 ms | 173032 KB | Output is correct |
95 | Correct | 1180 ms | 173032 KB | Output is correct |
96 | Correct | 840 ms | 173032 KB | Output is correct |
97 | Correct | 1167 ms | 173032 KB | Output is correct |
98 | Correct | 909 ms | 173032 KB | Output is correct |
99 | Correct | 1133 ms | 173032 KB | Output is correct |
100 | Correct | 177 ms | 173032 KB | Output is correct |
101 | Correct | 178 ms | 173032 KB | Output is correct |
102 | Correct | 140 ms | 173032 KB | Output is correct |
103 | Correct | 146 ms | 173032 KB | Output is correct |
104 | Correct | 142 ms | 173032 KB | Output is correct |
105 | Correct | 139 ms | 173032 KB | Output is correct |
106 | Correct | 1070 ms | 173032 KB | Output is correct |
107 | Correct | 1288 ms | 173032 KB | Output is correct |
108 | Correct | 940 ms | 173032 KB | Output is correct |
109 | Correct | 1036 ms | 173032 KB | Output is correct |
110 | Correct | 868 ms | 173032 KB | Output is correct |
111 | Correct | 1181 ms | 173032 KB | Output is correct |
112 | Correct | 169 ms | 173032 KB | Output is correct |
113 | Correct | 161 ms | 173032 KB | Output is correct |
114 | Correct | 165 ms | 173032 KB | Output is correct |
115 | Correct | 150 ms | 173032 KB | Output is correct |
116 | Correct | 122 ms | 173032 KB | Output is correct |
117 | Correct | 132 ms | 173032 KB | Output is correct |
118 | Correct | 983 ms | 173032 KB | Output is correct |
119 | Correct | 971 ms | 173032 KB | Output is correct |
120 | Correct | 1116 ms | 173032 KB | Output is correct |
121 | Correct | 949 ms | 173032 KB | Output is correct |
122 | Correct | 899 ms | 173032 KB | Output is correct |
123 | Correct | 1072 ms | 173032 KB | Output is correct |
124 | Correct | 1066 ms | 173032 KB | Output is correct |
125 | Correct | 898 ms | 173032 KB | Output is correct |
126 | Correct | 1045 ms | 173032 KB | Output is correct |