# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101114 | 2019-03-16T17:04:34 Z | gs14004 | Bitaro’s Party (JOI18_bitaro) | C++17 | 1484 ms | 244264 KB |
#include <cmath> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <map> #include <list> #include <time.h> #include <math.h> #include <random> #include <deque> #include <queue> #include <cassert> #include <unordered_map> #include <iomanip> #include <bitset> using namespace std; typedef long long lint; typedef pair<int, int> pi; const int MAXN = 100005; int n, m, q; vector<int> gph[MAXN]; vector<int> rev[MAXN]; int dp[MAXN]; vector<pi> low[MAXN]; int chk[MAXN]; int main(){ scanf("%d %d %d",&n,&m,&q); for(int i=0; i<m; i++){ int s, e; scanf("%d %d",&s,&e); gph[s].push_back(e); rev[e].push_back(s); } for(int i=1; i<=n; i++){ low[i].push_back(pi(0, i)); for(auto &j : rev[i]){ vector<pi> nxt = low[j]; vector<pi> prv = low[i]; low[i].clear(); int ptr = 0; for(auto &k : nxt){ k.first++; while(ptr < prv.size() && prv[ptr].first >= k.first){ if(chk[prv[ptr].second]){ ptr++; continue; } chk[prv[ptr].second] = 1; low[i].push_back(prv[ptr++]); } if(chk[k.second]) continue; chk[k.second] = 1; low[i].push_back(k); } while(ptr < prv.size()){ if(chk[prv[ptr].second]){ ptr++; continue; } chk[prv[ptr].second] = 1; low[i].push_back(prv[ptr++]); } for(auto &i : nxt) chk[i.second] = 0; for(auto &i : prv) chk[i.second] = 0; while(low[i].size() > 200) low[i].pop_back(); } } for(int i=0; i<q; i++){ int pos, k; scanf("%d %d",&pos,&k); vector<int> v(k); for(auto &i : v) scanf("%d",&i); for(auto &i : v) chk[i] = 1; int ans = -1; if(k >= 200){ fill(dp, dp + n + 1, -1e9); dp[pos] = 0; for(int j=pos; j; j--){ for(auto &k : gph[j]){ dp[j] = max(dp[j], dp[k] + 1); } if(chk[j] == 0) ans = max(ans, dp[j]); } } else{ for(auto &i : low[pos]){ if(!chk[i.second]){ ans = i.first; break; } } } printf("%d\n", ans); for(auto &i : v) chk[i] = 0; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 7296 KB | Output is correct |
2 | Correct | 9 ms | 7424 KB | Output is correct |
3 | Correct | 9 ms | 7424 KB | Output is correct |
4 | Correct | 11 ms | 7424 KB | Output is correct |
5 | Correct | 12 ms | 7808 KB | Output is correct |
6 | Correct | 15 ms | 7908 KB | Output is correct |
7 | Correct | 12 ms | 7936 KB | Output is correct |
8 | Correct | 15 ms | 9344 KB | Output is correct |
9 | Correct | 15 ms | 9316 KB | Output is correct |
10 | Correct | 15 ms | 9344 KB | Output is correct |
11 | Correct | 17 ms | 9216 KB | Output is correct |
12 | Correct | 15 ms | 8576 KB | Output is correct |
13 | Correct | 15 ms | 9216 KB | Output is correct |
14 | Correct | 16 ms | 8576 KB | Output is correct |
15 | Correct | 14 ms | 8192 KB | Output is correct |
16 | Correct | 14 ms | 8576 KB | Output is correct |
17 | Correct | 13 ms | 8676 KB | Output is correct |
18 | Correct | 14 ms | 8320 KB | Output is correct |
19 | Correct | 13 ms | 8832 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 7296 KB | Output is correct |
2 | Correct | 9 ms | 7424 KB | Output is correct |
3 | Correct | 9 ms | 7424 KB | Output is correct |
4 | Correct | 11 ms | 7424 KB | Output is correct |
5 | Correct | 12 ms | 7808 KB | Output is correct |
6 | Correct | 15 ms | 7908 KB | Output is correct |
7 | Correct | 12 ms | 7936 KB | Output is correct |
8 | Correct | 15 ms | 9344 KB | Output is correct |
9 | Correct | 15 ms | 9316 KB | Output is correct |
10 | Correct | 15 ms | 9344 KB | Output is correct |
11 | Correct | 17 ms | 9216 KB | Output is correct |
12 | Correct | 15 ms | 8576 KB | Output is correct |
13 | Correct | 15 ms | 9216 KB | Output is correct |
14 | Correct | 16 ms | 8576 KB | Output is correct |
15 | Correct | 14 ms | 8192 KB | Output is correct |
16 | Correct | 14 ms | 8576 KB | Output is correct |
17 | Correct | 13 ms | 8676 KB | Output is correct |
18 | Correct | 14 ms | 8320 KB | Output is correct |
19 | Correct | 13 ms | 8832 KB | Output is correct |
20 | Correct | 389 ms | 13048 KB | Output is correct |
21 | Correct | 400 ms | 13088 KB | Output is correct |
22 | Correct | 435 ms | 13080 KB | Output is correct |
23 | Correct | 473 ms | 13176 KB | Output is correct |
24 | Correct | 877 ms | 189656 KB | Output is correct |
25 | Correct | 913 ms | 181884 KB | Output is correct |
26 | Correct | 920 ms | 184184 KB | Output is correct |
27 | Correct | 886 ms | 219512 KB | Output is correct |
28 | Correct | 824 ms | 219440 KB | Output is correct |
29 | Correct | 898 ms | 219484 KB | Output is correct |
30 | Correct | 813 ms | 218688 KB | Output is correct |
31 | Correct | 964 ms | 236668 KB | Output is correct |
32 | Correct | 813 ms | 218488 KB | Output is correct |
33 | Correct | 712 ms | 142116 KB | Output is correct |
34 | Correct | 699 ms | 165880 KB | Output is correct |
35 | Correct | 698 ms | 141048 KB | Output is correct |
36 | Correct | 760 ms | 180400 KB | Output is correct |
37 | Correct | 814 ms | 197044 KB | Output is correct |
38 | Correct | 800 ms | 181028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 7296 KB | Output is correct |
2 | Correct | 9 ms | 7424 KB | Output is correct |
3 | Correct | 9 ms | 7424 KB | Output is correct |
4 | Correct | 11 ms | 7424 KB | Output is correct |
5 | Correct | 12 ms | 7808 KB | Output is correct |
6 | Correct | 15 ms | 7908 KB | Output is correct |
7 | Correct | 12 ms | 7936 KB | Output is correct |
8 | Correct | 15 ms | 9344 KB | Output is correct |
9 | Correct | 15 ms | 9316 KB | Output is correct |
10 | Correct | 15 ms | 9344 KB | Output is correct |
11 | Correct | 17 ms | 9216 KB | Output is correct |
12 | Correct | 15 ms | 8576 KB | Output is correct |
13 | Correct | 15 ms | 9216 KB | Output is correct |
14 | Correct | 16 ms | 8576 KB | Output is correct |
15 | Correct | 14 ms | 8192 KB | Output is correct |
16 | Correct | 14 ms | 8576 KB | Output is correct |
17 | Correct | 13 ms | 8676 KB | Output is correct |
18 | Correct | 14 ms | 8320 KB | Output is correct |
19 | Correct | 13 ms | 8832 KB | Output is correct |
20 | Correct | 389 ms | 13048 KB | Output is correct |
21 | Correct | 400 ms | 13088 KB | Output is correct |
22 | Correct | 435 ms | 13080 KB | Output is correct |
23 | Correct | 473 ms | 13176 KB | Output is correct |
24 | Correct | 877 ms | 189656 KB | Output is correct |
25 | Correct | 913 ms | 181884 KB | Output is correct |
26 | Correct | 920 ms | 184184 KB | Output is correct |
27 | Correct | 886 ms | 219512 KB | Output is correct |
28 | Correct | 824 ms | 219440 KB | Output is correct |
29 | Correct | 898 ms | 219484 KB | Output is correct |
30 | Correct | 813 ms | 218688 KB | Output is correct |
31 | Correct | 964 ms | 236668 KB | Output is correct |
32 | Correct | 813 ms | 218488 KB | Output is correct |
33 | Correct | 712 ms | 142116 KB | Output is correct |
34 | Correct | 699 ms | 165880 KB | Output is correct |
35 | Correct | 698 ms | 141048 KB | Output is correct |
36 | Correct | 760 ms | 180400 KB | Output is correct |
37 | Correct | 814 ms | 197044 KB | Output is correct |
38 | Correct | 800 ms | 181028 KB | Output is correct |
39 | Correct | 1156 ms | 192692 KB | Output is correct |
40 | Correct | 944 ms | 183544 KB | Output is correct |
41 | Correct | 868 ms | 186744 KB | Output is correct |
42 | Correct | 1219 ms | 186344 KB | Output is correct |
43 | Correct | 1016 ms | 193528 KB | Output is correct |
44 | Correct | 435 ms | 14324 KB | Output is correct |
45 | Correct | 456 ms | 13544 KB | Output is correct |
46 | Correct | 439 ms | 13372 KB | Output is correct |
47 | Correct | 445 ms | 13304 KB | Output is correct |
48 | Correct | 360 ms | 13048 KB | Output is correct |
49 | Correct | 927 ms | 220060 KB | Output is correct |
50 | Correct | 823 ms | 218744 KB | Output is correct |
51 | Correct | 388 ms | 14172 KB | Output is correct |
52 | Correct | 327 ms | 13304 KB | Output is correct |
53 | Correct | 873 ms | 180216 KB | Output is correct |
54 | Correct | 1012 ms | 199984 KB | Output is correct |
55 | Correct | 829 ms | 179252 KB | Output is correct |
56 | Correct | 1053 ms | 214512 KB | Output is correct |
57 | Correct | 526 ms | 14228 KB | Output is correct |
58 | Correct | 483 ms | 14124 KB | Output is correct |
59 | Correct | 483 ms | 13336 KB | Output is correct |
60 | Correct | 451 ms | 13276 KB | Output is correct |
61 | Correct | 1326 ms | 219332 KB | Output is correct |
62 | Correct | 898 ms | 180340 KB | Output is correct |
63 | Correct | 1046 ms | 195336 KB | Output is correct |
64 | Correct | 1232 ms | 219216 KB | Output is correct |
65 | Correct | 1376 ms | 179824 KB | Output is correct |
66 | Correct | 1438 ms | 196216 KB | Output is correct |
67 | Correct | 1484 ms | 219308 KB | Output is correct |
68 | Correct | 1202 ms | 180432 KB | Output is correct |
69 | Correct | 1383 ms | 198008 KB | Output is correct |
70 | Correct | 1006 ms | 219588 KB | Output is correct |
71 | Correct | 857 ms | 180496 KB | Output is correct |
72 | Correct | 872 ms | 199588 KB | Output is correct |
73 | Correct | 936 ms | 219448 KB | Output is correct |
74 | Correct | 904 ms | 180344 KB | Output is correct |
75 | Correct | 985 ms | 199800 KB | Output is correct |
76 | Correct | 923 ms | 220464 KB | Output is correct |
77 | Correct | 930 ms | 219544 KB | Output is correct |
78 | Correct | 915 ms | 219576 KB | Output is correct |
79 | Correct | 538 ms | 14404 KB | Output is correct |
80 | Correct | 450 ms | 13576 KB | Output is correct |
81 | Correct | 498 ms | 13076 KB | Output is correct |
82 | Correct | 1090 ms | 219476 KB | Output is correct |
83 | Correct | 1095 ms | 239220 KB | Output is correct |
84 | Correct | 962 ms | 218568 KB | Output is correct |
85 | Correct | 1205 ms | 240204 KB | Output is correct |
86 | Correct | 905 ms | 218624 KB | Output is correct |
87 | Correct | 1033 ms | 244264 KB | Output is correct |
88 | Correct | 437 ms | 14328 KB | Output is correct |
89 | Correct | 403 ms | 14252 KB | Output is correct |
90 | Correct | 376 ms | 13448 KB | Output is correct |
91 | Correct | 353 ms | 13436 KB | Output is correct |
92 | Correct | 349 ms | 13028 KB | Output is correct |
93 | Correct | 378 ms | 13136 KB | Output is correct |
94 | Correct | 809 ms | 142972 KB | Output is correct |
95 | Correct | 840 ms | 171652 KB | Output is correct |
96 | Correct | 837 ms | 141624 KB | Output is correct |
97 | Correct | 953 ms | 174420 KB | Output is correct |
98 | Correct | 788 ms | 142208 KB | Output is correct |
99 | Correct | 812 ms | 172284 KB | Output is correct |
100 | Correct | 529 ms | 14424 KB | Output is correct |
101 | Correct | 541 ms | 14412 KB | Output is correct |
102 | Correct | 485 ms | 13412 KB | Output is correct |
103 | Correct | 598 ms | 13544 KB | Output is correct |
104 | Correct | 494 ms | 13024 KB | Output is correct |
105 | Correct | 443 ms | 13048 KB | Output is correct |
106 | Correct | 910 ms | 180600 KB | Output is correct |
107 | Correct | 903 ms | 199416 KB | Output is correct |
108 | Correct | 903 ms | 180856 KB | Output is correct |
109 | Correct | 1093 ms | 203384 KB | Output is correct |
110 | Correct | 774 ms | 181152 KB | Output is correct |
111 | Correct | 883 ms | 192540 KB | Output is correct |
112 | Correct | 411 ms | 14308 KB | Output is correct |
113 | Correct | 446 ms | 14428 KB | Output is correct |
114 | Correct | 394 ms | 13432 KB | Output is correct |
115 | Correct | 489 ms | 13432 KB | Output is correct |
116 | Correct | 421 ms | 13048 KB | Output is correct |
117 | Correct | 419 ms | 13060 KB | Output is correct |
118 | Correct | 907 ms | 218872 KB | Output is correct |
119 | Correct | 769 ms | 180220 KB | Output is correct |
120 | Correct | 905 ms | 193912 KB | Output is correct |
121 | Correct | 927 ms | 219000 KB | Output is correct |
122 | Correct | 868 ms | 179612 KB | Output is correct |
123 | Correct | 931 ms | 198432 KB | Output is correct |
124 | Correct | 913 ms | 218912 KB | Output is correct |
125 | Correct | 843 ms | 180560 KB | Output is correct |
126 | Correct | 929 ms | 198412 KB | Output is correct |