# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
45034 | 2018-04-11T04:27:39 Z | ikura355 | Bitaro’s Party (JOI18_bitaro) | C++14 | 1257 ms | 251408 KB |
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define X first #define Y second const int maxn = 1e5 + 5; const int block = 310; const int inf = maxn+5; int n,m,q; vector<int> way[maxn]; int p[maxn], busy[maxn]; bool vis[maxn]; pii rec[maxn][311], temp[311]; int dp[maxn]; void small_init() { for(int u=1;u<=n;u++) { for(int i=0;i<block;i++) rec[u][i] = {-inf, 0}; rec[u][0] = {0, u}; for(auto v : way[u]) { for(int i=0;i<block;i++) temp[i] = {-inf, 0}; //merge int pos,i,j; pos = i = j = 0; vis[0] = 1; while(pos<block && (i<block || j<block)) { // printf("\t%d: merge %d and %d : %d or %d\n",pos,u,v,i,j); //choose maximum if(j>=block || rec[u][i].X > rec[v][j].X+1) { if(!vis[rec[u][i].Y]) temp[pos++] = {rec[u][i].X, rec[u][i].Y}; vis[rec[u][i].Y] = 1; ++i; } else { if(!vis[rec[v][j].Y]) temp[pos++] = {rec[v][j].X+1, rec[v][j].Y}; vis[rec[v][j].Y] = 1; ++j; } } for(int i=0;i<block;i++) vis[rec[u][i].Y] = vis[rec[v][i].Y] = 0; for(int i=0;i<block;i++) rec[u][i] = temp[i]; } // printf("dest = %d\n",u); // for(int i=0;i<block;i++) printf("\t{%d, %d}\n",rec[u][i].X,rec[u][i].Y); } } int small_solve(int u) { int ans = -1; for(int i=0;i<block;i++) { if(!busy[rec[u][i].Y]) { ans = rec[u][i].X; break; } } if(ans<0) return -1; return ans; } int large_solve(int pos) { for(int u=1;u<=pos;u++) { if(busy[u]) dp[u] = -inf; else dp[u] = 0; for(auto v : way[u]) dp[u] = max(dp[u], dp[v]+1); } if(dp[pos]<0) return -1; return dp[pos]; } int main() { scanf("%d%d%d",&n,&m,&q); for(int i=0;i<m;i++) { int u, v; scanf("%d%d",&u,&v); way[v].push_back(u); } small_init(); while(q--) { int u, k; scanf("%d%d",&u,&k); for(int i=0;i<k;i++) scanf("%d",&p[i]); for(int i=0;i<k;i++) busy[p[i]] = 1; if(k < block) printf("%d\n",small_solve(u)); else printf("%d\n",large_solve(u)); for(int i=0;i<k;i++) busy[p[i]] = 0; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2880 KB | Output is correct |
3 | Correct | 4 ms | 2880 KB | Output is correct |
4 | Correct | 4 ms | 2956 KB | Output is correct |
5 | Correct | 13 ms | 5444 KB | Output is correct |
6 | Correct | 12 ms | 5468 KB | Output is correct |
7 | Correct | 12 ms | 5468 KB | Output is correct |
8 | Correct | 12 ms | 5528 KB | Output is correct |
9 | Correct | 12 ms | 5528 KB | Output is correct |
10 | Correct | 12 ms | 5528 KB | Output is correct |
11 | Correct | 13 ms | 5528 KB | Output is correct |
12 | Correct | 11 ms | 5528 KB | Output is correct |
13 | Correct | 12 ms | 5528 KB | Output is correct |
14 | Correct | 12 ms | 5528 KB | Output is correct |
15 | Correct | 12 ms | 5528 KB | Output is correct |
16 | Correct | 12 ms | 5528 KB | Output is correct |
17 | Correct | 13 ms | 5528 KB | Output is correct |
18 | Correct | 13 ms | 5528 KB | Output is correct |
19 | Correct | 14 ms | 5528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2880 KB | Output is correct |
3 | Correct | 4 ms | 2880 KB | Output is correct |
4 | Correct | 4 ms | 2956 KB | Output is correct |
5 | Correct | 13 ms | 5444 KB | Output is correct |
6 | Correct | 12 ms | 5468 KB | Output is correct |
7 | Correct | 12 ms | 5468 KB | Output is correct |
8 | Correct | 12 ms | 5528 KB | Output is correct |
9 | Correct | 12 ms | 5528 KB | Output is correct |
10 | Correct | 12 ms | 5528 KB | Output is correct |
11 | Correct | 13 ms | 5528 KB | Output is correct |
12 | Correct | 11 ms | 5528 KB | Output is correct |
13 | Correct | 12 ms | 5528 KB | Output is correct |
14 | Correct | 12 ms | 5528 KB | Output is correct |
15 | Correct | 12 ms | 5528 KB | Output is correct |
16 | Correct | 12 ms | 5528 KB | Output is correct |
17 | Correct | 13 ms | 5528 KB | Output is correct |
18 | Correct | 13 ms | 5528 KB | Output is correct |
19 | Correct | 14 ms | 5528 KB | Output is correct |
20 | Correct | 613 ms | 6652 KB | Output is correct |
21 | Correct | 532 ms | 6756 KB | Output is correct |
22 | Correct | 627 ms | 6808 KB | Output is correct |
23 | Correct | 591 ms | 6808 KB | Output is correct |
24 | Correct | 1122 ms | 250144 KB | Output is correct |
25 | Correct | 1144 ms | 250272 KB | Output is correct |
26 | Correct | 1124 ms | 250272 KB | Output is correct |
27 | Correct | 825 ms | 250620 KB | Output is correct |
28 | Correct | 794 ms | 250620 KB | Output is correct |
29 | Correct | 810 ms | 250620 KB | Output is correct |
30 | Correct | 803 ms | 250620 KB | Output is correct |
31 | Correct | 886 ms | 250620 KB | Output is correct |
32 | Correct | 796 ms | 250620 KB | Output is correct |
33 | Correct | 842 ms | 250620 KB | Output is correct |
34 | Correct | 814 ms | 250620 KB | Output is correct |
35 | Correct | 821 ms | 250620 KB | Output is correct |
36 | Correct | 819 ms | 250620 KB | Output is correct |
37 | Correct | 912 ms | 250620 KB | Output is correct |
38 | Correct | 878 ms | 250620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2880 KB | Output is correct |
3 | Correct | 4 ms | 2880 KB | Output is correct |
4 | Correct | 4 ms | 2956 KB | Output is correct |
5 | Correct | 13 ms | 5444 KB | Output is correct |
6 | Correct | 12 ms | 5468 KB | Output is correct |
7 | Correct | 12 ms | 5468 KB | Output is correct |
8 | Correct | 12 ms | 5528 KB | Output is correct |
9 | Correct | 12 ms | 5528 KB | Output is correct |
10 | Correct | 12 ms | 5528 KB | Output is correct |
11 | Correct | 13 ms | 5528 KB | Output is correct |
12 | Correct | 11 ms | 5528 KB | Output is correct |
13 | Correct | 12 ms | 5528 KB | Output is correct |
14 | Correct | 12 ms | 5528 KB | Output is correct |
15 | Correct | 12 ms | 5528 KB | Output is correct |
16 | Correct | 12 ms | 5528 KB | Output is correct |
17 | Correct | 13 ms | 5528 KB | Output is correct |
18 | Correct | 13 ms | 5528 KB | Output is correct |
19 | Correct | 14 ms | 5528 KB | Output is correct |
20 | Correct | 613 ms | 6652 KB | Output is correct |
21 | Correct | 532 ms | 6756 KB | Output is correct |
22 | Correct | 627 ms | 6808 KB | Output is correct |
23 | Correct | 591 ms | 6808 KB | Output is correct |
24 | Correct | 1122 ms | 250144 KB | Output is correct |
25 | Correct | 1144 ms | 250272 KB | Output is correct |
26 | Correct | 1124 ms | 250272 KB | Output is correct |
27 | Correct | 825 ms | 250620 KB | Output is correct |
28 | Correct | 794 ms | 250620 KB | Output is correct |
29 | Correct | 810 ms | 250620 KB | Output is correct |
30 | Correct | 803 ms | 250620 KB | Output is correct |
31 | Correct | 886 ms | 250620 KB | Output is correct |
32 | Correct | 796 ms | 250620 KB | Output is correct |
33 | Correct | 842 ms | 250620 KB | Output is correct |
34 | Correct | 814 ms | 250620 KB | Output is correct |
35 | Correct | 821 ms | 250620 KB | Output is correct |
36 | Correct | 819 ms | 250620 KB | Output is correct |
37 | Correct | 912 ms | 250620 KB | Output is correct |
38 | Correct | 878 ms | 250620 KB | Output is correct |
39 | Correct | 1174 ms | 250620 KB | Output is correct |
40 | Correct | 1178 ms | 250620 KB | Output is correct |
41 | Correct | 1179 ms | 250620 KB | Output is correct |
42 | Correct | 1257 ms | 250620 KB | Output is correct |
43 | Correct | 1193 ms | 250620 KB | Output is correct |
44 | Correct | 668 ms | 250620 KB | Output is correct |
45 | Correct | 618 ms | 250620 KB | Output is correct |
46 | Correct | 633 ms | 250620 KB | Output is correct |
47 | Correct | 623 ms | 250620 KB | Output is correct |
48 | Correct | 602 ms | 250620 KB | Output is correct |
49 | Correct | 858 ms | 250620 KB | Output is correct |
50 | Correct | 797 ms | 250620 KB | Output is correct |
51 | Correct | 584 ms | 250620 KB | Output is correct |
52 | Correct | 524 ms | 250620 KB | Output is correct |
53 | Correct | 856 ms | 250620 KB | Output is correct |
54 | Correct | 933 ms | 250620 KB | Output is correct |
55 | Correct | 807 ms | 250620 KB | Output is correct |
56 | Correct | 901 ms | 250620 KB | Output is correct |
57 | Correct | 639 ms | 250620 KB | Output is correct |
58 | Correct | 674 ms | 250620 KB | Output is correct |
59 | Correct | 595 ms | 250620 KB | Output is correct |
60 | Correct | 620 ms | 250620 KB | Output is correct |
61 | Correct | 874 ms | 250620 KB | Output is correct |
62 | Correct | 854 ms | 250620 KB | Output is correct |
63 | Correct | 1010 ms | 250620 KB | Output is correct |
64 | Correct | 1057 ms | 250620 KB | Output is correct |
65 | Correct | 1010 ms | 250620 KB | Output is correct |
66 | Correct | 1153 ms | 250620 KB | Output is correct |
67 | Correct | 812 ms | 250620 KB | Output is correct |
68 | Correct | 908 ms | 250620 KB | Output is correct |
69 | Correct | 867 ms | 250620 KB | Output is correct |
70 | Correct | 794 ms | 250840 KB | Output is correct |
71 | Correct | 844 ms | 250840 KB | Output is correct |
72 | Correct | 912 ms | 250840 KB | Output is correct |
73 | Correct | 841 ms | 250968 KB | Output is correct |
74 | Correct | 824 ms | 250968 KB | Output is correct |
75 | Correct | 904 ms | 250968 KB | Output is correct |
76 | Correct | 890 ms | 251408 KB | Output is correct |
77 | Correct | 817 ms | 251408 KB | Output is correct |
78 | Correct | 815 ms | 251408 KB | Output is correct |
79 | Correct | 560 ms | 251408 KB | Output is correct |
80 | Correct | 555 ms | 251408 KB | Output is correct |
81 | Correct | 537 ms | 251408 KB | Output is correct |
82 | Correct | 991 ms | 251408 KB | Output is correct |
83 | Correct | 1062 ms | 251408 KB | Output is correct |
84 | Correct | 902 ms | 251408 KB | Output is correct |
85 | Correct | 953 ms | 251408 KB | Output is correct |
86 | Correct | 891 ms | 251408 KB | Output is correct |
87 | Correct | 1006 ms | 251408 KB | Output is correct |
88 | Correct | 661 ms | 251408 KB | Output is correct |
89 | Correct | 685 ms | 251408 KB | Output is correct |
90 | Correct | 615 ms | 251408 KB | Output is correct |
91 | Correct | 648 ms | 251408 KB | Output is correct |
92 | Correct | 601 ms | 251408 KB | Output is correct |
93 | Correct | 612 ms | 251408 KB | Output is correct |
94 | Correct | 987 ms | 251408 KB | Output is correct |
95 | Correct | 1108 ms | 251408 KB | Output is correct |
96 | Correct | 903 ms | 251408 KB | Output is correct |
97 | Correct | 988 ms | 251408 KB | Output is correct |
98 | Correct | 909 ms | 251408 KB | Output is correct |
99 | Correct | 1086 ms | 251408 KB | Output is correct |
100 | Correct | 647 ms | 251408 KB | Output is correct |
101 | Correct | 620 ms | 251408 KB | Output is correct |
102 | Correct | 730 ms | 251408 KB | Output is correct |
103 | Correct | 618 ms | 251408 KB | Output is correct |
104 | Correct | 613 ms | 251408 KB | Output is correct |
105 | Correct | 608 ms | 251408 KB | Output is correct |
106 | Correct | 899 ms | 251408 KB | Output is correct |
107 | Correct | 920 ms | 251408 KB | Output is correct |
108 | Correct | 838 ms | 251408 KB | Output is correct |
109 | Correct | 832 ms | 251408 KB | Output is correct |
110 | Correct | 844 ms | 251408 KB | Output is correct |
111 | Correct | 920 ms | 251408 KB | Output is correct |
112 | Correct | 643 ms | 251408 KB | Output is correct |
113 | Correct | 668 ms | 251408 KB | Output is correct |
114 | Correct | 572 ms | 251408 KB | Output is correct |
115 | Correct | 619 ms | 251408 KB | Output is correct |
116 | Correct | 583 ms | 251408 KB | Output is correct |
117 | Correct | 628 ms | 251408 KB | Output is correct |
118 | Correct | 792 ms | 251408 KB | Output is correct |
119 | Correct | 864 ms | 251408 KB | Output is correct |
120 | Correct | 911 ms | 251408 KB | Output is correct |
121 | Correct | 831 ms | 251408 KB | Output is correct |
122 | Correct | 811 ms | 251408 KB | Output is correct |
123 | Correct | 915 ms | 251408 KB | Output is correct |
124 | Correct | 808 ms | 251408 KB | Output is correct |
125 | Correct | 794 ms | 251408 KB | Output is correct |
126 | Correct | 891 ms | 251408 KB | Output is correct |