# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
322559 | 2020-11-14T20:49:17 Z | NachoLibre | Bitaro’s Party (JOI18_bitaro) | C++14 | 1815 ms | 416572 KB |
#include <bits/stdc++.h> using namespace std; const int B = 301, N = 100005, M = 200005, Q = N, S = N; int n, m, q, x, y, c[S], dpn[N]; bool dk[N], gb[N]; vector<int> v[N][2]; vector<pair<int, int> > dp[N]; void G(vector<pair<int, int> > &a, vector<pair<int, int> > b) { vector<pair<int, int> > c = a; int bp = 0, cp = 0; a.clear(); while((bp < b.size() || cp < c.size()) && a.size() < B) { if(bp == b.size()) { if(!gb[c[cp].second]) a.push_back(c[cp]); gb[c[cp].second] = 1; ++cp; } else if(cp == c.size()) { if(!gb[b[bp].second]) a.push_back({b[bp].first + 1, b[bp].second}); gb[b[bp].second] = 1; ++bp; } else if(b[bp].first + 1 < c[cp].first) { if(!gb[c[cp].second]) a.push_back(c[cp]); gb[c[cp].second] = 1; ++cp; } else { if(!gb[b[bp].second]) a.push_back({b[bp].first + 1, b[bp].second}); gb[b[bp].second] = 1; ++bp; } } for(int i = 0; i < a.size(); ++i) { gb[a[i].second] = 0; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; for(int i = 1; i <= m; ++i) { cin >> x >> y; v[x][1].push_back(y); v[y][0].push_back(x); } for(int i = 1; i <= n; ++i) { dp[i].push_back({0, i}); for(int j = 0; j < v[i][0].size(); ++j) { G(dp[i], dp[v[i][0][j]]); } // for(int j = 0; j < dp[i].size(); ++j) { // cout << "[] " << dp[i][j].first << " " << dp[i][j].second << "\n"; // } // cout << "\n"; } for(int qi = 1; qi <= q; ++qi) { cin >> x >> y; for(int i = 0; i < y; ++i) { cin >> c[i]; dk[c[i]] = 1; } if(y < B) { int ap = -1; for(int i = 0; i < dp[x].size(); ++i) { if(!dk[dp[x][i].second]) { ap = dp[x][i].first; break; } } cout << ap << "\n"; } else { for(int i = 1; i <= x; ++i) { dpn[i] = 0; for(int j = 0; j < v[i][0].size(); ++j) { dpn[i] = max(dpn[i], dpn[v[i][0][j]] + 1); } if(!dpn[i] && dk[i]) dpn[i] = -1; } cout << dpn[x] << "\n"; } for(int i = 0; i < y; ++i) { dk[c[i]] = 0; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7404 KB | Output is correct |
2 | Correct | 5 ms | 7404 KB | Output is correct |
3 | Correct | 5 ms | 7424 KB | Output is correct |
4 | Correct | 5 ms | 7404 KB | Output is correct |
5 | Correct | 7 ms | 7916 KB | Output is correct |
6 | Correct | 7 ms | 7916 KB | Output is correct |
7 | Correct | 7 ms | 7916 KB | Output is correct |
8 | Correct | 16 ms | 10988 KB | Output is correct |
9 | Correct | 16 ms | 10988 KB | Output is correct |
10 | Correct | 16 ms | 10988 KB | Output is correct |
11 | Correct | 16 ms | 10476 KB | Output is correct |
12 | Correct | 12 ms | 8812 KB | Output is correct |
13 | Correct | 16 ms | 10368 KB | Output is correct |
14 | Correct | 15 ms | 9452 KB | Output is correct |
15 | Correct | 10 ms | 8428 KB | Output is correct |
16 | Correct | 13 ms | 9452 KB | Output is correct |
17 | Correct | 13 ms | 9708 KB | Output is correct |
18 | Correct | 10 ms | 8684 KB | Output is correct |
19 | Correct | 13 ms | 9740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7404 KB | Output is correct |
2 | Correct | 5 ms | 7404 KB | Output is correct |
3 | Correct | 5 ms | 7424 KB | Output is correct |
4 | Correct | 5 ms | 7404 KB | Output is correct |
5 | Correct | 7 ms | 7916 KB | Output is correct |
6 | Correct | 7 ms | 7916 KB | Output is correct |
7 | Correct | 7 ms | 7916 KB | Output is correct |
8 | Correct | 16 ms | 10988 KB | Output is correct |
9 | Correct | 16 ms | 10988 KB | Output is correct |
10 | Correct | 16 ms | 10988 KB | Output is correct |
11 | Correct | 16 ms | 10476 KB | Output is correct |
12 | Correct | 12 ms | 8812 KB | Output is correct |
13 | Correct | 16 ms | 10368 KB | Output is correct |
14 | Correct | 15 ms | 9452 KB | Output is correct |
15 | Correct | 10 ms | 8428 KB | Output is correct |
16 | Correct | 13 ms | 9452 KB | Output is correct |
17 | Correct | 13 ms | 9708 KB | Output is correct |
18 | Correct | 10 ms | 8684 KB | Output is correct |
19 | Correct | 13 ms | 9740 KB | Output is correct |
20 | Correct | 875 ms | 13420 KB | Output is correct |
21 | Correct | 762 ms | 13292 KB | Output is correct |
22 | Correct | 868 ms | 13420 KB | Output is correct |
23 | Correct | 903 ms | 13304 KB | Output is correct |
24 | Correct | 1108 ms | 257304 KB | Output is correct |
25 | Correct | 1119 ms | 269084 KB | Output is correct |
26 | Correct | 1115 ms | 268140 KB | Output is correct |
27 | Correct | 1467 ms | 416564 KB | Output is correct |
28 | Correct | 1457 ms | 416568 KB | Output is correct |
29 | Correct | 1460 ms | 416492 KB | Output is correct |
30 | Correct | 1433 ms | 415212 KB | Output is correct |
31 | Correct | 1438 ms | 400756 KB | Output is correct |
32 | Correct | 1448 ms | 415340 KB | Output is correct |
33 | Correct | 979 ms | 258004 KB | Output is correct |
34 | Correct | 888 ms | 211948 KB | Output is correct |
35 | Correct | 974 ms | 256108 KB | Output is correct |
36 | Correct | 1152 ms | 337004 KB | Output is correct |
37 | Correct | 1093 ms | 305644 KB | Output is correct |
38 | Correct | 1134 ms | 337968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7404 KB | Output is correct |
2 | Correct | 5 ms | 7404 KB | Output is correct |
3 | Correct | 5 ms | 7424 KB | Output is correct |
4 | Correct | 5 ms | 7404 KB | Output is correct |
5 | Correct | 7 ms | 7916 KB | Output is correct |
6 | Correct | 7 ms | 7916 KB | Output is correct |
7 | Correct | 7 ms | 7916 KB | Output is correct |
8 | Correct | 16 ms | 10988 KB | Output is correct |
9 | Correct | 16 ms | 10988 KB | Output is correct |
10 | Correct | 16 ms | 10988 KB | Output is correct |
11 | Correct | 16 ms | 10476 KB | Output is correct |
12 | Correct | 12 ms | 8812 KB | Output is correct |
13 | Correct | 16 ms | 10368 KB | Output is correct |
14 | Correct | 15 ms | 9452 KB | Output is correct |
15 | Correct | 10 ms | 8428 KB | Output is correct |
16 | Correct | 13 ms | 9452 KB | Output is correct |
17 | Correct | 13 ms | 9708 KB | Output is correct |
18 | Correct | 10 ms | 8684 KB | Output is correct |
19 | Correct | 13 ms | 9740 KB | Output is correct |
20 | Correct | 875 ms | 13420 KB | Output is correct |
21 | Correct | 762 ms | 13292 KB | Output is correct |
22 | Correct | 868 ms | 13420 KB | Output is correct |
23 | Correct | 903 ms | 13304 KB | Output is correct |
24 | Correct | 1108 ms | 257304 KB | Output is correct |
25 | Correct | 1119 ms | 269084 KB | Output is correct |
26 | Correct | 1115 ms | 268140 KB | Output is correct |
27 | Correct | 1467 ms | 416564 KB | Output is correct |
28 | Correct | 1457 ms | 416568 KB | Output is correct |
29 | Correct | 1460 ms | 416492 KB | Output is correct |
30 | Correct | 1433 ms | 415212 KB | Output is correct |
31 | Correct | 1438 ms | 400756 KB | Output is correct |
32 | Correct | 1448 ms | 415340 KB | Output is correct |
33 | Correct | 979 ms | 258004 KB | Output is correct |
34 | Correct | 888 ms | 211948 KB | Output is correct |
35 | Correct | 974 ms | 256108 KB | Output is correct |
36 | Correct | 1152 ms | 337004 KB | Output is correct |
37 | Correct | 1093 ms | 305644 KB | Output is correct |
38 | Correct | 1134 ms | 337968 KB | Output is correct |
39 | Correct | 1116 ms | 260588 KB | Output is correct |
40 | Correct | 1100 ms | 262892 KB | Output is correct |
41 | Correct | 1093 ms | 265564 KB | Output is correct |
42 | Correct | 1230 ms | 264040 KB | Output is correct |
43 | Correct | 1082 ms | 263276 KB | Output is correct |
44 | Correct | 894 ms | 13856 KB | Output is correct |
45 | Correct | 864 ms | 13676 KB | Output is correct |
46 | Correct | 857 ms | 13496 KB | Output is correct |
47 | Correct | 859 ms | 13548 KB | Output is correct |
48 | Correct | 847 ms | 13328 KB | Output is correct |
49 | Correct | 1476 ms | 416468 KB | Output is correct |
50 | Correct | 1435 ms | 416048 KB | Output is correct |
51 | Correct | 799 ms | 13676 KB | Output is correct |
52 | Correct | 771 ms | 13292 KB | Output is correct |
53 | Correct | 1199 ms | 335724 KB | Output is correct |
54 | Correct | 1179 ms | 305772 KB | Output is correct |
55 | Correct | 1139 ms | 335724 KB | Output is correct |
56 | Correct | 1113 ms | 306452 KB | Output is correct |
57 | Correct | 867 ms | 13804 KB | Output is correct |
58 | Correct | 900 ms | 13804 KB | Output is correct |
59 | Correct | 828 ms | 13292 KB | Output is correct |
60 | Correct | 861 ms | 13260 KB | Output is correct |
61 | Correct | 1551 ms | 416348 KB | Output is correct |
62 | Correct | 1287 ms | 337516 KB | Output is correct |
63 | Correct | 1227 ms | 305004 KB | Output is correct |
64 | Correct | 1815 ms | 416468 KB | Output is correct |
65 | Correct | 1545 ms | 335852 KB | Output is correct |
66 | Correct | 1516 ms | 306752 KB | Output is correct |
67 | Correct | 1429 ms | 415900 KB | Output is correct |
68 | Correct | 1143 ms | 336876 KB | Output is correct |
69 | Correct | 1095 ms | 302260 KB | Output is correct |
70 | Correct | 1469 ms | 416236 KB | Output is correct |
71 | Correct | 1179 ms | 337264 KB | Output is correct |
72 | Correct | 1132 ms | 306092 KB | Output is correct |
73 | Correct | 1484 ms | 416396 KB | Output is correct |
74 | Correct | 1206 ms | 337260 KB | Output is correct |
75 | Correct | 1140 ms | 306028 KB | Output is correct |
76 | Correct | 1496 ms | 416572 KB | Output is correct |
77 | Correct | 1447 ms | 415980 KB | Output is correct |
78 | Correct | 1440 ms | 416492 KB | Output is correct |
79 | Correct | 800 ms | 13608 KB | Output is correct |
80 | Correct | 771 ms | 13292 KB | Output is correct |
81 | Correct | 764 ms | 13292 KB | Output is correct |
82 | Correct | 1481 ms | 415468 KB | Output is correct |
83 | Correct | 1460 ms | 400972 KB | Output is correct |
84 | Correct | 1420 ms | 414768 KB | Output is correct |
85 | Correct | 1409 ms | 400036 KB | Output is correct |
86 | Correct | 1417 ms | 414956 KB | Output is correct |
87 | Correct | 1427 ms | 401516 KB | Output is correct |
88 | Correct | 876 ms | 13804 KB | Output is correct |
89 | Correct | 906 ms | 13712 KB | Output is correct |
90 | Correct | 853 ms | 13348 KB | Output is correct |
91 | Correct | 869 ms | 13420 KB | Output is correct |
92 | Correct | 850 ms | 13372 KB | Output is correct |
93 | Correct | 860 ms | 13292 KB | Output is correct |
94 | Correct | 1035 ms | 258468 KB | Output is correct |
95 | Correct | 931 ms | 210796 KB | Output is correct |
96 | Correct | 983 ms | 256492 KB | Output is correct |
97 | Correct | 934 ms | 214636 KB | Output is correct |
98 | Correct | 1000 ms | 257752 KB | Output is correct |
99 | Correct | 905 ms | 214228 KB | Output is correct |
100 | Correct | 937 ms | 13676 KB | Output is correct |
101 | Correct | 940 ms | 13612 KB | Output is correct |
102 | Correct | 906 ms | 13352 KB | Output is correct |
103 | Correct | 913 ms | 13292 KB | Output is correct |
104 | Correct | 935 ms | 13316 KB | Output is correct |
105 | Correct | 902 ms | 13304 KB | Output is correct |
106 | Correct | 1226 ms | 335980 KB | Output is correct |
107 | Correct | 1154 ms | 305900 KB | Output is correct |
108 | Correct | 1155 ms | 337900 KB | Output is correct |
109 | Correct | 1095 ms | 305260 KB | Output is correct |
110 | Correct | 1165 ms | 338220 KB | Output is correct |
111 | Correct | 1116 ms | 306592 KB | Output is correct |
112 | Correct | 875 ms | 13688 KB | Output is correct |
113 | Correct | 905 ms | 13548 KB | Output is correct |
114 | Correct | 847 ms | 13292 KB | Output is correct |
115 | Correct | 879 ms | 13420 KB | Output is correct |
116 | Correct | 862 ms | 13164 KB | Output is correct |
117 | Correct | 865 ms | 13192 KB | Output is correct |
118 | Correct | 1432 ms | 415940 KB | Output is correct |
119 | Correct | 1177 ms | 337632 KB | Output is correct |
120 | Correct | 1118 ms | 304960 KB | Output is correct |
121 | Correct | 1428 ms | 415916 KB | Output is correct |
122 | Correct | 1159 ms | 336236 KB | Output is correct |
123 | Correct | 1098 ms | 305132 KB | Output is correct |
124 | Correct | 1427 ms | 416108 KB | Output is correct |
125 | Correct | 1163 ms | 337872 KB | Output is correct |
126 | Correct | 1093 ms | 304176 KB | Output is correct |