# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
185426 | 2020-01-11T14:04:56 Z | Akashi | Bitaro’s Party (JOI18_bitaro) | C++14 | 1272 ms | 177088 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1e5; const int K = 200; int n, m, q; bool viz[N + 5]; int h[N + 5], a[N + 5], dist[N + 5]; pair <int, int> d[N + 5][K + 5]; vector <int> v[N + 5], vt[N + 5]; vector <int> aux; inline bool cmp(int x, int y){return dist[x] > dist[y];} int main() { scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n ; ++i) for(int j = 1; j <= K ; ++j) d[i][j] = {-1, -1}; int x, y; for(int i = 1; i <= m ; ++i){ scanf("%d%d", &x, &y); v[x].push_back(y); vt[y].push_back(x); } for(int i = 1; i <= n ; ++i){ aux.clear(); aux.push_back(i); dist[0] = 0; for(auto it : vt[i]){ for(int k = 1; k <= K ; ++k){ if(d[it][k].first == -1) break ; int nod = d[it][k].second; dist[nod] = max(dist[nod], d[it][k].first + 1); if(!viz[nod]) viz[nod] = 1, aux.push_back(nod); } } sort(aux.begin(), aux.end(), cmp); for(int j = 1; j <= K && j <= aux.size() ; ++j) d[i][j] = {dist[aux[j - 1]], aux[j - 1]}; for(auto it : aux) viz[it] = dist[it] = 0; } while(q--){ scanf("%d%d", &x, &y); for(int i = 1; i <= y ; ++i){ scanf("%d", &a[i]); viz[a[i]] = 1; } int ans = -2; for(int i = 1; i <= K ; ++i){ if(d[x][i].first == -1) {ans = -1; break ;} if(!viz[d[x][i].second]) {ans = d[x][i].first; break ;} } if(ans == -2){ ans = -1; dist[x] = 0; if(!viz[x]) ans = 0; for(int i = x - 1; i >= 1 ; --i){ dist[i] = -30000000; for(auto it : v[i]) if(it <= x) dist[i] = max(dist[i], dist[it] + 1); if(!viz[i]) ans = max(dist[i], ans); } } printf("%d\n", ans); for(int i = 1; i <= y ; ++i) viz[a[i]] = 0; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5112 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 3 ms | 4988 KB | Output is correct |
5 | Correct | 14 ms | 6776 KB | Output is correct |
6 | Correct | 10 ms | 6648 KB | Output is correct |
7 | Correct | 10 ms | 6648 KB | Output is correct |
8 | Correct | 14 ms | 6648 KB | Output is correct |
9 | Correct | 13 ms | 6648 KB | Output is correct |
10 | Correct | 11 ms | 6648 KB | Output is correct |
11 | Correct | 13 ms | 6648 KB | Output is correct |
12 | Correct | 12 ms | 6732 KB | Output is correct |
13 | Correct | 10 ms | 6648 KB | Output is correct |
14 | Correct | 13 ms | 6648 KB | Output is correct |
15 | Correct | 11 ms | 6648 KB | Output is correct |
16 | Correct | 13 ms | 6648 KB | Output is correct |
17 | Correct | 22 ms | 6904 KB | Output is correct |
18 | Correct | 12 ms | 6648 KB | Output is correct |
19 | Correct | 15 ms | 6648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5112 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 3 ms | 4988 KB | Output is correct |
5 | Correct | 14 ms | 6776 KB | Output is correct |
6 | Correct | 10 ms | 6648 KB | Output is correct |
7 | Correct | 10 ms | 6648 KB | Output is correct |
8 | Correct | 14 ms | 6648 KB | Output is correct |
9 | Correct | 13 ms | 6648 KB | Output is correct |
10 | Correct | 11 ms | 6648 KB | Output is correct |
11 | Correct | 13 ms | 6648 KB | Output is correct |
12 | Correct | 12 ms | 6732 KB | Output is correct |
13 | Correct | 10 ms | 6648 KB | Output is correct |
14 | Correct | 13 ms | 6648 KB | Output is correct |
15 | Correct | 11 ms | 6648 KB | Output is correct |
16 | Correct | 13 ms | 6648 KB | Output is correct |
17 | Correct | 22 ms | 6904 KB | Output is correct |
18 | Correct | 12 ms | 6648 KB | Output is correct |
19 | Correct | 15 ms | 6648 KB | Output is correct |
20 | Correct | 152 ms | 9080 KB | Output is correct |
21 | Correct | 176 ms | 9208 KB | Output is correct |
22 | Correct | 175 ms | 8996 KB | Output is correct |
23 | Correct | 195 ms | 9208 KB | Output is correct |
24 | Correct | 1131 ms | 171692 KB | Output is correct |
25 | Correct | 1175 ms | 173904 KB | Output is correct |
26 | Correct | 1160 ms | 174028 KB | Output is correct |
27 | Correct | 891 ms | 175532 KB | Output is correct |
28 | Correct | 951 ms | 175428 KB | Output is correct |
29 | Correct | 883 ms | 175576 KB | Output is correct |
30 | Correct | 892 ms | 174964 KB | Output is correct |
31 | Correct | 1085 ms | 174888 KB | Output is correct |
32 | Correct | 936 ms | 174840 KB | Output is correct |
33 | Correct | 869 ms | 174840 KB | Output is correct |
34 | Correct | 995 ms | 174844 KB | Output is correct |
35 | Correct | 928 ms | 174884 KB | Output is correct |
36 | Correct | 1094 ms | 174908 KB | Output is correct |
37 | Correct | 1103 ms | 174968 KB | Output is correct |
38 | Correct | 1000 ms | 174968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5112 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 3 ms | 4988 KB | Output is correct |
5 | Correct | 14 ms | 6776 KB | Output is correct |
6 | Correct | 10 ms | 6648 KB | Output is correct |
7 | Correct | 10 ms | 6648 KB | Output is correct |
8 | Correct | 14 ms | 6648 KB | Output is correct |
9 | Correct | 13 ms | 6648 KB | Output is correct |
10 | Correct | 11 ms | 6648 KB | Output is correct |
11 | Correct | 13 ms | 6648 KB | Output is correct |
12 | Correct | 12 ms | 6732 KB | Output is correct |
13 | Correct | 10 ms | 6648 KB | Output is correct |
14 | Correct | 13 ms | 6648 KB | Output is correct |
15 | Correct | 11 ms | 6648 KB | Output is correct |
16 | Correct | 13 ms | 6648 KB | Output is correct |
17 | Correct | 22 ms | 6904 KB | Output is correct |
18 | Correct | 12 ms | 6648 KB | Output is correct |
19 | Correct | 15 ms | 6648 KB | Output is correct |
20 | Correct | 152 ms | 9080 KB | Output is correct |
21 | Correct | 176 ms | 9208 KB | Output is correct |
22 | Correct | 175 ms | 8996 KB | Output is correct |
23 | Correct | 195 ms | 9208 KB | Output is correct |
24 | Correct | 1131 ms | 171692 KB | Output is correct |
25 | Correct | 1175 ms | 173904 KB | Output is correct |
26 | Correct | 1160 ms | 174028 KB | Output is correct |
27 | Correct | 891 ms | 175532 KB | Output is correct |
28 | Correct | 951 ms | 175428 KB | Output is correct |
29 | Correct | 883 ms | 175576 KB | Output is correct |
30 | Correct | 892 ms | 174964 KB | Output is correct |
31 | Correct | 1085 ms | 174888 KB | Output is correct |
32 | Correct | 936 ms | 174840 KB | Output is correct |
33 | Correct | 869 ms | 174840 KB | Output is correct |
34 | Correct | 995 ms | 174844 KB | Output is correct |
35 | Correct | 928 ms | 174884 KB | Output is correct |
36 | Correct | 1094 ms | 174908 KB | Output is correct |
37 | Correct | 1103 ms | 174968 KB | Output is correct |
38 | Correct | 1000 ms | 174968 KB | Output is correct |
39 | Correct | 1191 ms | 174992 KB | Output is correct |
40 | Correct | 1160 ms | 174416 KB | Output is correct |
41 | Correct | 1152 ms | 174108 KB | Output is correct |
42 | Correct | 1165 ms | 174088 KB | Output is correct |
43 | Correct | 1151 ms | 174200 KB | Output is correct |
44 | Correct | 220 ms | 11992 KB | Output is correct |
45 | Correct | 189 ms | 11000 KB | Output is correct |
46 | Correct | 184 ms | 11168 KB | Output is correct |
47 | Correct | 180 ms | 10752 KB | Output is correct |
48 | Correct | 176 ms | 10620 KB | Output is correct |
49 | Correct | 946 ms | 176760 KB | Output is correct |
50 | Correct | 894 ms | 175480 KB | Output is correct |
51 | Correct | 208 ms | 11788 KB | Output is correct |
52 | Correct | 186 ms | 11100 KB | Output is correct |
53 | Correct | 1051 ms | 175940 KB | Output is correct |
54 | Correct | 1245 ms | 175728 KB | Output is correct |
55 | Correct | 1008 ms | 174840 KB | Output is correct |
56 | Correct | 1095 ms | 174852 KB | Output is correct |
57 | Correct | 222 ms | 11872 KB | Output is correct |
58 | Correct | 214 ms | 11768 KB | Output is correct |
59 | Correct | 187 ms | 10864 KB | Output is correct |
60 | Correct | 193 ms | 10840 KB | Output is correct |
61 | Correct | 1000 ms | 175572 KB | Output is correct |
62 | Correct | 1118 ms | 174968 KB | Output is correct |
63 | Correct | 1118 ms | 174832 KB | Output is correct |
64 | Correct | 1248 ms | 175520 KB | Output is correct |
65 | Correct | 1272 ms | 174780 KB | Output is correct |
66 | Correct | 1139 ms | 174964 KB | Output is correct |
67 | Correct | 1168 ms | 175392 KB | Output is correct |
68 | Correct | 1216 ms | 174968 KB | Output is correct |
69 | Correct | 1088 ms | 174988 KB | Output is correct |
70 | Correct | 900 ms | 175480 KB | Output is correct |
71 | Correct | 1016 ms | 175112 KB | Output is correct |
72 | Correct | 1193 ms | 174836 KB | Output is correct |
73 | Correct | 992 ms | 175560 KB | Output is correct |
74 | Correct | 1047 ms | 174920 KB | Output is correct |
75 | Correct | 1108 ms | 174912 KB | Output is correct |
76 | Correct | 948 ms | 177088 KB | Output is correct |
77 | Correct | 911 ms | 175736 KB | Output is correct |
78 | Correct | 895 ms | 175736 KB | Output is correct |
79 | Correct | 220 ms | 12152 KB | Output is correct |
80 | Correct | 191 ms | 11128 KB | Output is correct |
81 | Correct | 174 ms | 10588 KB | Output is correct |
82 | Correct | 1055 ms | 176200 KB | Output is correct |
83 | Correct | 1159 ms | 176052 KB | Output is correct |
84 | Correct | 946 ms | 174852 KB | Output is correct |
85 | Correct | 1106 ms | 174840 KB | Output is correct |
86 | Correct | 912 ms | 174968 KB | Output is correct |
87 | Correct | 1087 ms | 174916 KB | Output is correct |
88 | Correct | 220 ms | 12036 KB | Output is correct |
89 | Correct | 225 ms | 11896 KB | Output is correct |
90 | Correct | 186 ms | 11132 KB | Output is correct |
91 | Correct | 169 ms | 11256 KB | Output is correct |
92 | Correct | 178 ms | 10616 KB | Output is correct |
93 | Correct | 173 ms | 10616 KB | Output is correct |
94 | Correct | 954 ms | 176220 KB | Output is correct |
95 | Correct | 1087 ms | 176188 KB | Output is correct |
96 | Correct | 888 ms | 175024 KB | Output is correct |
97 | Correct | 1039 ms | 175084 KB | Output is correct |
98 | Correct | 867 ms | 174968 KB | Output is correct |
99 | Correct | 995 ms | 174968 KB | Output is correct |
100 | Correct | 232 ms | 11896 KB | Output is correct |
101 | Correct | 231 ms | 12080 KB | Output is correct |
102 | Correct | 202 ms | 11000 KB | Output is correct |
103 | Correct | 200 ms | 11000 KB | Output is correct |
104 | Correct | 188 ms | 10616 KB | Output is correct |
105 | Correct | 189 ms | 10616 KB | Output is correct |
106 | Correct | 1068 ms | 176256 KB | Output is correct |
107 | Correct | 1149 ms | 176192 KB | Output is correct |
108 | Correct | 1031 ms | 175068 KB | Output is correct |
109 | Correct | 1061 ms | 175024 KB | Output is correct |
110 | Correct | 989 ms | 175096 KB | Output is correct |
111 | Correct | 1161 ms | 175272 KB | Output is correct |
112 | Correct | 219 ms | 12124 KB | Output is correct |
113 | Correct | 221 ms | 12044 KB | Output is correct |
114 | Correct | 186 ms | 11000 KB | Output is correct |
115 | Correct | 185 ms | 11000 KB | Output is correct |
116 | Correct | 176 ms | 10712 KB | Output is correct |
117 | Correct | 175 ms | 10552 KB | Output is correct |
118 | Correct | 887 ms | 175256 KB | Output is correct |
119 | Correct | 1000 ms | 174676 KB | Output is correct |
120 | Correct | 1094 ms | 174860 KB | Output is correct |
121 | Correct | 893 ms | 175452 KB | Output is correct |
122 | Correct | 1035 ms | 174840 KB | Output is correct |
123 | Correct | 1084 ms | 174740 KB | Output is correct |
124 | Correct | 888 ms | 175404 KB | Output is correct |
125 | Correct | 1025 ms | 174936 KB | Output is correct |
126 | Correct | 1156 ms | 174840 KB | Output is correct |