# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
62730 | 2018-07-29T22:27:26 Z | kingpig9 | Bitaro’s Party (JOI18_bitaro) | C++11 | 1988 ms | 416788 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5 + 10; const int SQRT = 320; #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) int N, M, Q; vector<int> adj[MAXN], radj[MAXN]; vector<pii> far[MAXN]; //farthest SQRT vertices: pair(dist, vertex) pii tmp[2 * SQRT]; bool vis[MAXN]; void merge (vector<pii> &v, const vector<pii> &w) { int sz = merge(all(v), all(w), tmp, greater<pii> ()) - tmp; v.clear(); for (int i = 0; i < sz && v.size() < SQRT; i++) { if (!vis[tmp[i].se]) { v.push_back(tmp[i]); vis[tmp[i].se] = true; } } for (pii p : v) { vis[p.se] = false; } } bool busy[MAXN]; int dp[MAXN]; int main() { scanf("%d %d %d", &N, &M, &Q); for (int i = 1; i <= M; i++) { int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); radj[y].push_back(x); } for (int i = 1; i <= N; i++) { far[i].push_back({0, i}); for (int j : radj[i]) { vector<pii> vtmp = far[j]; for (pii &p : vtmp) { p.fi++; } merge(far[i], vtmp); } } //if size >= SQRT then brute force for (int qi = 1; qi <= Q; qi++) { int x, sz; scanf("%d %d", &x, &sz); vector<int> vbusy(sz); for (int &c : vbusy) { scanf("%d", &c); busy[c] = true; } int ans = -1; if (sz < SQRT) { //the farthest away -- one of them will not be for (pii p : far[x]) { if (!busy[p.se]) { ans = p.fi; break; } } } else { //brute force dp[x] = 0; for (int i = x - 1; i >= 1; i--) { dp[i] = -1e9; } for (int i = x; i >= 1; i--) { for (int j : radj[i]) { dp[j] = max(dp[j], dp[i] + 1); } if (!busy[i]) { ans = max(ans, dp[i]); } } } printf("%d\n", ans); for (int c : vbusy) { busy[c] = false; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7412 KB | Output is correct |
3 | Correct | 9 ms | 7432 KB | Output is correct |
4 | Correct | 9 ms | 7432 KB | Output is correct |
5 | Correct | 12 ms | 7960 KB | Output is correct |
6 | Correct | 13 ms | 8016 KB | Output is correct |
7 | Correct | 11 ms | 8016 KB | Output is correct |
8 | Correct | 20 ms | 10964 KB | Output is correct |
9 | Correct | 21 ms | 11092 KB | Output is correct |
10 | Correct | 23 ms | 11168 KB | Output is correct |
11 | Correct | 20 ms | 11168 KB | Output is correct |
12 | Correct | 14 ms | 11168 KB | Output is correct |
13 | Correct | 18 ms | 11168 KB | Output is correct |
14 | Correct | 19 ms | 11168 KB | Output is correct |
15 | Correct | 13 ms | 11168 KB | Output is correct |
16 | Correct | 15 ms | 11168 KB | Output is correct |
17 | Correct | 16 ms | 11168 KB | Output is correct |
18 | Correct | 14 ms | 11168 KB | Output is correct |
19 | Correct | 18 ms | 11168 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7412 KB | Output is correct |
3 | Correct | 9 ms | 7432 KB | Output is correct |
4 | Correct | 9 ms | 7432 KB | Output is correct |
5 | Correct | 12 ms | 7960 KB | Output is correct |
6 | Correct | 13 ms | 8016 KB | Output is correct |
7 | Correct | 11 ms | 8016 KB | Output is correct |
8 | Correct | 20 ms | 10964 KB | Output is correct |
9 | Correct | 21 ms | 11092 KB | Output is correct |
10 | Correct | 23 ms | 11168 KB | Output is correct |
11 | Correct | 20 ms | 11168 KB | Output is correct |
12 | Correct | 14 ms | 11168 KB | Output is correct |
13 | Correct | 18 ms | 11168 KB | Output is correct |
14 | Correct | 19 ms | 11168 KB | Output is correct |
15 | Correct | 13 ms | 11168 KB | Output is correct |
16 | Correct | 15 ms | 11168 KB | Output is correct |
17 | Correct | 16 ms | 11168 KB | Output is correct |
18 | Correct | 14 ms | 11168 KB | Output is correct |
19 | Correct | 18 ms | 11168 KB | Output is correct |
20 | Correct | 667 ms | 13292 KB | Output is correct |
21 | Correct | 554 ms | 13348 KB | Output is correct |
22 | Correct | 697 ms | 13372 KB | Output is correct |
23 | Correct | 782 ms | 13372 KB | Output is correct |
24 | Correct | 1224 ms | 259708 KB | Output is correct |
25 | Correct | 1269 ms | 271480 KB | Output is correct |
26 | Correct | 1272 ms | 271480 KB | Output is correct |
27 | Correct | 1182 ms | 416572 KB | Output is correct |
28 | Correct | 1259 ms | 416688 KB | Output is correct |
29 | Correct | 1248 ms | 416688 KB | Output is correct |
30 | Correct | 1269 ms | 416688 KB | Output is correct |
31 | Correct | 1362 ms | 416688 KB | Output is correct |
32 | Correct | 1303 ms | 416688 KB | Output is correct |
33 | Correct | 955 ms | 416688 KB | Output is correct |
34 | Correct | 879 ms | 416688 KB | Output is correct |
35 | Correct | 965 ms | 416688 KB | Output is correct |
36 | Correct | 1091 ms | 416688 KB | Output is correct |
37 | Correct | 1106 ms | 416688 KB | Output is correct |
38 | Correct | 1130 ms | 416688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7288 KB | Output is correct |
2 | Correct | 9 ms | 7412 KB | Output is correct |
3 | Correct | 9 ms | 7432 KB | Output is correct |
4 | Correct | 9 ms | 7432 KB | Output is correct |
5 | Correct | 12 ms | 7960 KB | Output is correct |
6 | Correct | 13 ms | 8016 KB | Output is correct |
7 | Correct | 11 ms | 8016 KB | Output is correct |
8 | Correct | 20 ms | 10964 KB | Output is correct |
9 | Correct | 21 ms | 11092 KB | Output is correct |
10 | Correct | 23 ms | 11168 KB | Output is correct |
11 | Correct | 20 ms | 11168 KB | Output is correct |
12 | Correct | 14 ms | 11168 KB | Output is correct |
13 | Correct | 18 ms | 11168 KB | Output is correct |
14 | Correct | 19 ms | 11168 KB | Output is correct |
15 | Correct | 13 ms | 11168 KB | Output is correct |
16 | Correct | 15 ms | 11168 KB | Output is correct |
17 | Correct | 16 ms | 11168 KB | Output is correct |
18 | Correct | 14 ms | 11168 KB | Output is correct |
19 | Correct | 18 ms | 11168 KB | Output is correct |
20 | Correct | 667 ms | 13292 KB | Output is correct |
21 | Correct | 554 ms | 13348 KB | Output is correct |
22 | Correct | 697 ms | 13372 KB | Output is correct |
23 | Correct | 782 ms | 13372 KB | Output is correct |
24 | Correct | 1224 ms | 259708 KB | Output is correct |
25 | Correct | 1269 ms | 271480 KB | Output is correct |
26 | Correct | 1272 ms | 271480 KB | Output is correct |
27 | Correct | 1182 ms | 416572 KB | Output is correct |
28 | Correct | 1259 ms | 416688 KB | Output is correct |
29 | Correct | 1248 ms | 416688 KB | Output is correct |
30 | Correct | 1269 ms | 416688 KB | Output is correct |
31 | Correct | 1362 ms | 416688 KB | Output is correct |
32 | Correct | 1303 ms | 416688 KB | Output is correct |
33 | Correct | 955 ms | 416688 KB | Output is correct |
34 | Correct | 879 ms | 416688 KB | Output is correct |
35 | Correct | 965 ms | 416688 KB | Output is correct |
36 | Correct | 1091 ms | 416688 KB | Output is correct |
37 | Correct | 1106 ms | 416688 KB | Output is correct |
38 | Correct | 1130 ms | 416688 KB | Output is correct |
39 | Correct | 1379 ms | 416688 KB | Output is correct |
40 | Correct | 1381 ms | 416688 KB | Output is correct |
41 | Correct | 1361 ms | 416688 KB | Output is correct |
42 | Correct | 1474 ms | 416688 KB | Output is correct |
43 | Correct | 1410 ms | 416688 KB | Output is correct |
44 | Correct | 729 ms | 416688 KB | Output is correct |
45 | Correct | 711 ms | 416688 KB | Output is correct |
46 | Correct | 702 ms | 416688 KB | Output is correct |
47 | Correct | 689 ms | 416688 KB | Output is correct |
48 | Correct | 676 ms | 416688 KB | Output is correct |
49 | Correct | 1794 ms | 416772 KB | Output is correct |
50 | Correct | 1629 ms | 416772 KB | Output is correct |
51 | Correct | 574 ms | 416772 KB | Output is correct |
52 | Correct | 544 ms | 416772 KB | Output is correct |
53 | Correct | 1114 ms | 416772 KB | Output is correct |
54 | Correct | 1164 ms | 416772 KB | Output is correct |
55 | Correct | 1137 ms | 416772 KB | Output is correct |
56 | Correct | 1225 ms | 416772 KB | Output is correct |
57 | Correct | 714 ms | 416772 KB | Output is correct |
58 | Correct | 769 ms | 416772 KB | Output is correct |
59 | Correct | 634 ms | 416772 KB | Output is correct |
60 | Correct | 686 ms | 416772 KB | Output is correct |
61 | Correct | 1324 ms | 416772 KB | Output is correct |
62 | Correct | 1340 ms | 416772 KB | Output is correct |
63 | Correct | 1323 ms | 416772 KB | Output is correct |
64 | Correct | 1988 ms | 416772 KB | Output is correct |
65 | Correct | 1481 ms | 416772 KB | Output is correct |
66 | Correct | 1443 ms | 416772 KB | Output is correct |
67 | Correct | 1645 ms | 416772 KB | Output is correct |
68 | Correct | 1089 ms | 416772 KB | Output is correct |
69 | Correct | 1159 ms | 416772 KB | Output is correct |
70 | Correct | 1571 ms | 416772 KB | Output is correct |
71 | Correct | 1061 ms | 416772 KB | Output is correct |
72 | Correct | 1121 ms | 416772 KB | Output is correct |
73 | Correct | 1592 ms | 416772 KB | Output is correct |
74 | Correct | 1125 ms | 416772 KB | Output is correct |
75 | Correct | 1113 ms | 416772 KB | Output is correct |
76 | Correct | 1643 ms | 416772 KB | Output is correct |
77 | Correct | 1534 ms | 416772 KB | Output is correct |
78 | Correct | 1589 ms | 416788 KB | Output is correct |
79 | Correct | 571 ms | 416788 KB | Output is correct |
80 | Correct | 545 ms | 416788 KB | Output is correct |
81 | Correct | 549 ms | 416788 KB | Output is correct |
82 | Correct | 1301 ms | 416788 KB | Output is correct |
83 | Correct | 1306 ms | 416788 KB | Output is correct |
84 | Correct | 1550 ms | 416788 KB | Output is correct |
85 | Correct | 1320 ms | 416788 KB | Output is correct |
86 | Correct | 1245 ms | 416788 KB | Output is correct |
87 | Correct | 1346 ms | 416788 KB | Output is correct |
88 | Correct | 713 ms | 416788 KB | Output is correct |
89 | Correct | 748 ms | 416788 KB | Output is correct |
90 | Correct | 700 ms | 416788 KB | Output is correct |
91 | Correct | 735 ms | 416788 KB | Output is correct |
92 | Correct | 712 ms | 416788 KB | Output is correct |
93 | Correct | 707 ms | 416788 KB | Output is correct |
94 | Correct | 1072 ms | 416788 KB | Output is correct |
95 | Correct | 1056 ms | 416788 KB | Output is correct |
96 | Correct | 1006 ms | 416788 KB | Output is correct |
97 | Correct | 915 ms | 416788 KB | Output is correct |
98 | Correct | 932 ms | 416788 KB | Output is correct |
99 | Correct | 900 ms | 416788 KB | Output is correct |
100 | Correct | 907 ms | 416788 KB | Output is correct |
101 | Correct | 840 ms | 416788 KB | Output is correct |
102 | Correct | 846 ms | 416788 KB | Output is correct |
103 | Correct | 863 ms | 416788 KB | Output is correct |
104 | Correct | 867 ms | 416788 KB | Output is correct |
105 | Correct | 842 ms | 416788 KB | Output is correct |
106 | Correct | 1199 ms | 416788 KB | Output is correct |
107 | Correct | 1212 ms | 416788 KB | Output is correct |
108 | Correct | 1067 ms | 416788 KB | Output is correct |
109 | Correct | 1128 ms | 416788 KB | Output is correct |
110 | Correct | 1140 ms | 416788 KB | Output is correct |
111 | Correct | 1332 ms | 416788 KB | Output is correct |
112 | Correct | 735 ms | 416788 KB | Output is correct |
113 | Correct | 754 ms | 416788 KB | Output is correct |
114 | Correct | 717 ms | 416788 KB | Output is correct |
115 | Correct | 731 ms | 416788 KB | Output is correct |
116 | Correct | 712 ms | 416788 KB | Output is correct |
117 | Correct | 723 ms | 416788 KB | Output is correct |
118 | Correct | 1666 ms | 416788 KB | Output is correct |
119 | Correct | 1184 ms | 416788 KB | Output is correct |
120 | Correct | 1234 ms | 416788 KB | Output is correct |
121 | Correct | 1672 ms | 416788 KB | Output is correct |
122 | Correct | 1099 ms | 416788 KB | Output is correct |
123 | Correct | 1257 ms | 416788 KB | Output is correct |
124 | Correct | 1694 ms | 416788 KB | Output is correct |
125 | Correct | 1113 ms | 416788 KB | Output is correct |
126 | Correct | 1156 ms | 416788 KB | Output is correct |