# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
220914 | 2020-04-09T08:59:00 Z | patrikpavic2 | Bitaro’s Party (JOI18_bitaro) | C++17 | 1290 ms | 117364 KB |
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define X first #define Y second #define PB push_back using namespace std; const int N = 1e5 + 500; const int INF = 0x3f3f3f3f; const int K = 100; typedef pair < int, int > pii; vector < pii > tko[N]; vector < int > v[N], r[N]; int dis[N], zab[N], n, m, q, uso[N], gdje[N]; priority_queue < pii > Q; void spoji(int x){ for(int y : r[x]){ gdje[y] = 0; Q.push({tko[y][0].X, y}); } for(;(!Q.empty()) && tko[x].size() < K;){ int vrh = Q.top().Y; if(!uso[tko[vrh][gdje[vrh]].Y]){ uso[tko[vrh][gdje[vrh]].Y] = 1; tko[x].PB(tko[vrh][gdje[vrh]]); } Q.pop(); gdje[vrh]++; if(gdje[vrh] < (int)tko[vrh].size()) Q.push({tko[vrh][gdje[vrh]].X, vrh}); } for(;!Q.empty();) Q.pop(); for(pii &tmp : tko[x]) uso[tmp.Y] = 0, tmp.X++; if(tko[x].size() < K) tko[x].PB({0, x}); } void precompute(){ for(int i = 1;i <= n;i++) spoji(i); } int seljacki(int x){ for(int i = 1;i <= n;i++) dis[i] = -INF; dis[x] = 0; int ret = -1; for(int i = x; i ; i--){ for(int j : v[i]) dis[i] = max(dis[i], dis[j] + 1); if(!zab[i]) ret = max(ret, dis[i]); } return ret; } int main(){ scanf("%d%d%d", &n, &m, &q); for(;m--;){ int x, y; scanf("%d%d", &x, &y); v[x].PB(y); r[y].PB(x); } precompute(); for(;q--;){ int st; scanf("%d", &st); int kol; scanf("%d", &kol); vector < int > tmp; for(;kol--;){ int x; scanf("%d", &x); tmp.PB(x); zab[x] = 1; } if((int)tmp.size() >= K) printf("%d\n", seljacki(st)); else{ int ret = -1; for(pii bla : tko[st]) if(!zab[bla.Y]) ret = max(ret, bla.X); printf("%d\n", ret); } for(int x : tmp) zab[x] = 0; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7424 KB | Output is correct |
2 | Correct | 8 ms | 7424 KB | Output is correct |
3 | Correct | 9 ms | 7424 KB | Output is correct |
4 | Correct | 8 ms | 7424 KB | Output is correct |
5 | Correct | 14 ms | 8064 KB | Output is correct |
6 | Correct | 13 ms | 7936 KB | Output is correct |
7 | Correct | 12 ms | 7808 KB | Output is correct |
8 | Correct | 14 ms | 8448 KB | Output is correct |
9 | Correct | 14 ms | 8448 KB | Output is correct |
10 | Correct | 15 ms | 8448 KB | Output is correct |
11 | Correct | 15 ms | 8448 KB | Output is correct |
12 | Correct | 13 ms | 8192 KB | Output is correct |
13 | Correct | 15 ms | 8448 KB | Output is correct |
14 | Correct | 13 ms | 8064 KB | Output is correct |
15 | Correct | 12 ms | 7936 KB | Output is correct |
16 | Correct | 13 ms | 8064 KB | Output is correct |
17 | Correct | 14 ms | 8192 KB | Output is correct |
18 | Correct | 12 ms | 8064 KB | Output is correct |
19 | Correct | 14 ms | 8192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7424 KB | Output is correct |
2 | Correct | 8 ms | 7424 KB | Output is correct |
3 | Correct | 9 ms | 7424 KB | Output is correct |
4 | Correct | 8 ms | 7424 KB | Output is correct |
5 | Correct | 14 ms | 8064 KB | Output is correct |
6 | Correct | 13 ms | 7936 KB | Output is correct |
7 | Correct | 12 ms | 7808 KB | Output is correct |
8 | Correct | 14 ms | 8448 KB | Output is correct |
9 | Correct | 14 ms | 8448 KB | Output is correct |
10 | Correct | 15 ms | 8448 KB | Output is correct |
11 | Correct | 15 ms | 8448 KB | Output is correct |
12 | Correct | 13 ms | 8192 KB | Output is correct |
13 | Correct | 15 ms | 8448 KB | Output is correct |
14 | Correct | 13 ms | 8064 KB | Output is correct |
15 | Correct | 12 ms | 7936 KB | Output is correct |
16 | Correct | 13 ms | 8064 KB | Output is correct |
17 | Correct | 14 ms | 8192 KB | Output is correct |
18 | Correct | 12 ms | 8064 KB | Output is correct |
19 | Correct | 14 ms | 8192 KB | Output is correct |
20 | Correct | 364 ms | 10832 KB | Output is correct |
21 | Correct | 245 ms | 10616 KB | Output is correct |
22 | Correct | 355 ms | 10616 KB | Output is correct |
23 | Correct | 188 ms | 10744 KB | Output is correct |
24 | Correct | 672 ms | 92020 KB | Output is correct |
25 | Correct | 704 ms | 93456 KB | Output is correct |
26 | Correct | 697 ms | 93124 KB | Output is correct |
27 | Correct | 666 ms | 117364 KB | Output is correct |
28 | Correct | 672 ms | 117364 KB | Output is correct |
29 | Correct | 652 ms | 117108 KB | Output is correct |
30 | Correct | 655 ms | 116600 KB | Output is correct |
31 | Correct | 680 ms | 114804 KB | Output is correct |
32 | Correct | 660 ms | 116344 KB | Output is correct |
33 | Correct | 482 ms | 79352 KB | Output is correct |
34 | Correct | 481 ms | 72180 KB | Output is correct |
35 | Correct | 491 ms | 78700 KB | Output is correct |
36 | Correct | 569 ms | 98164 KB | Output is correct |
37 | Correct | 575 ms | 93688 KB | Output is correct |
38 | Correct | 577 ms | 98136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7424 KB | Output is correct |
2 | Correct | 8 ms | 7424 KB | Output is correct |
3 | Correct | 9 ms | 7424 KB | Output is correct |
4 | Correct | 8 ms | 7424 KB | Output is correct |
5 | Correct | 14 ms | 8064 KB | Output is correct |
6 | Correct | 13 ms | 7936 KB | Output is correct |
7 | Correct | 12 ms | 7808 KB | Output is correct |
8 | Correct | 14 ms | 8448 KB | Output is correct |
9 | Correct | 14 ms | 8448 KB | Output is correct |
10 | Correct | 15 ms | 8448 KB | Output is correct |
11 | Correct | 15 ms | 8448 KB | Output is correct |
12 | Correct | 13 ms | 8192 KB | Output is correct |
13 | Correct | 15 ms | 8448 KB | Output is correct |
14 | Correct | 13 ms | 8064 KB | Output is correct |
15 | Correct | 12 ms | 7936 KB | Output is correct |
16 | Correct | 13 ms | 8064 KB | Output is correct |
17 | Correct | 14 ms | 8192 KB | Output is correct |
18 | Correct | 12 ms | 8064 KB | Output is correct |
19 | Correct | 14 ms | 8192 KB | Output is correct |
20 | Correct | 364 ms | 10832 KB | Output is correct |
21 | Correct | 245 ms | 10616 KB | Output is correct |
22 | Correct | 355 ms | 10616 KB | Output is correct |
23 | Correct | 188 ms | 10744 KB | Output is correct |
24 | Correct | 672 ms | 92020 KB | Output is correct |
25 | Correct | 704 ms | 93456 KB | Output is correct |
26 | Correct | 697 ms | 93124 KB | Output is correct |
27 | Correct | 666 ms | 117364 KB | Output is correct |
28 | Correct | 672 ms | 117364 KB | Output is correct |
29 | Correct | 652 ms | 117108 KB | Output is correct |
30 | Correct | 655 ms | 116600 KB | Output is correct |
31 | Correct | 680 ms | 114804 KB | Output is correct |
32 | Correct | 660 ms | 116344 KB | Output is correct |
33 | Correct | 482 ms | 79352 KB | Output is correct |
34 | Correct | 481 ms | 72180 KB | Output is correct |
35 | Correct | 491 ms | 78700 KB | Output is correct |
36 | Correct | 569 ms | 98164 KB | Output is correct |
37 | Correct | 575 ms | 93688 KB | Output is correct |
38 | Correct | 577 ms | 98136 KB | Output is correct |
39 | Correct | 768 ms | 92000 KB | Output is correct |
40 | Correct | 730 ms | 92392 KB | Output is correct |
41 | Correct | 1290 ms | 93048 KB | Output is correct |
42 | Correct | 828 ms | 92792 KB | Output is correct |
43 | Correct | 706 ms | 92280 KB | Output is correct |
44 | Correct | 476 ms | 11116 KB | Output is correct |
45 | Correct | 382 ms | 10744 KB | Output is correct |
46 | Correct | 468 ms | 10616 KB | Output is correct |
47 | Correct | 383 ms | 10820 KB | Output is correct |
48 | Correct | 376 ms | 10744 KB | Output is correct |
49 | Correct | 748 ms | 116984 KB | Output is correct |
50 | Correct | 1235 ms | 116728 KB | Output is correct |
51 | Correct | 324 ms | 11256 KB | Output is correct |
52 | Correct | 358 ms | 10620 KB | Output is correct |
53 | Correct | 660 ms | 97328 KB | Output is correct |
54 | Correct | 664 ms | 93052 KB | Output is correct |
55 | Correct | 1126 ms | 97528 KB | Output is correct |
56 | Correct | 1112 ms | 93304 KB | Output is correct |
57 | Correct | 409 ms | 11384 KB | Output is correct |
58 | Correct | 423 ms | 11000 KB | Output is correct |
59 | Correct | 461 ms | 10872 KB | Output is correct |
60 | Correct | 463 ms | 10616 KB | Output is correct |
61 | Correct | 758 ms | 116596 KB | Output is correct |
62 | Correct | 683 ms | 97788 KB | Output is correct |
63 | Correct | 673 ms | 92712 KB | Output is correct |
64 | Correct | 996 ms | 116600 KB | Output is correct |
65 | Correct | 880 ms | 97632 KB | Output is correct |
66 | Correct | 885 ms | 93408 KB | Output is correct |
67 | Correct | 1204 ms | 116804 KB | Output is correct |
68 | Correct | 1110 ms | 97980 KB | Output is correct |
69 | Correct | 1096 ms | 92240 KB | Output is correct |
70 | Correct | 695 ms | 116984 KB | Output is correct |
71 | Correct | 591 ms | 97656 KB | Output is correct |
72 | Correct | 599 ms | 92916 KB | Output is correct |
73 | Correct | 692 ms | 116856 KB | Output is correct |
74 | Correct | 629 ms | 97656 KB | Output is correct |
75 | Correct | 603 ms | 92792 KB | Output is correct |
76 | Correct | 758 ms | 117308 KB | Output is correct |
77 | Correct | 1216 ms | 117196 KB | Output is correct |
78 | Correct | 673 ms | 117168 KB | Output is correct |
79 | Correct | 326 ms | 11092 KB | Output is correct |
80 | Correct | 358 ms | 10616 KB | Output is correct |
81 | Correct | 259 ms | 10744 KB | Output is correct |
82 | Correct | 754 ms | 116344 KB | Output is correct |
83 | Correct | 762 ms | 114296 KB | Output is correct |
84 | Correct | 1159 ms | 116344 KB | Output is correct |
85 | Correct | 1194 ms | 114168 KB | Output is correct |
86 | Correct | 656 ms | 116488 KB | Output is correct |
87 | Correct | 693 ms | 114740 KB | Output is correct |
88 | Correct | 402 ms | 11000 KB | Output is correct |
89 | Correct | 447 ms | 11256 KB | Output is correct |
90 | Correct | 465 ms | 10744 KB | Output is correct |
91 | Correct | 489 ms | 10832 KB | Output is correct |
92 | Correct | 363 ms | 10616 KB | Output is correct |
93 | Correct | 378 ms | 10756 KB | Output is correct |
94 | Correct | 566 ms | 79096 KB | Output is correct |
95 | Correct | 551 ms | 71416 KB | Output is correct |
96 | Correct | 960 ms | 78836 KB | Output is correct |
97 | Correct | 958 ms | 72592 KB | Output is correct |
98 | Correct | 521 ms | 79352 KB | Output is correct |
99 | Correct | 498 ms | 72560 KB | Output is correct |
100 | Correct | 290 ms | 11000 KB | Output is correct |
101 | Correct | 268 ms | 11004 KB | Output is correct |
102 | Correct | 314 ms | 10804 KB | Output is correct |
103 | Correct | 275 ms | 10652 KB | Output is correct |
104 | Correct | 208 ms | 10744 KB | Output is correct |
105 | Correct | 195 ms | 10688 KB | Output is correct |
106 | Correct | 681 ms | 97784 KB | Output is correct |
107 | Correct | 674 ms | 93304 KB | Output is correct |
108 | Correct | 1094 ms | 98168 KB | Output is correct |
109 | Correct | 1130 ms | 93100 KB | Output is correct |
110 | Correct | 610 ms | 98592 KB | Output is correct |
111 | Correct | 614 ms | 93748 KB | Output is correct |
112 | Correct | 405 ms | 11128 KB | Output is correct |
113 | Correct | 439 ms | 11000 KB | Output is correct |
114 | Correct | 451 ms | 10616 KB | Output is correct |
115 | Correct | 473 ms | 10744 KB | Output is correct |
116 | Correct | 342 ms | 10744 KB | Output is correct |
117 | Correct | 373 ms | 10872 KB | Output is correct |
118 | Correct | 667 ms | 116220 KB | Output is correct |
119 | Correct | 595 ms | 97484 KB | Output is correct |
120 | Correct | 585 ms | 92408 KB | Output is correct |
121 | Correct | 676 ms | 116192 KB | Output is correct |
122 | Correct | 585 ms | 97016 KB | Output is correct |
123 | Correct | 609 ms | 92408 KB | Output is correct |
124 | Correct | 681 ms | 116216 KB | Output is correct |
125 | Correct | 598 ms | 97528 KB | Output is correct |
126 | Correct | 587 ms | 92264 KB | Output is correct |