# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
43969 | 2018-03-29T01:22:16 Z | model_code | Bitaro’s Party (JOI18_bitaro) | C++17 | 1432 ms | 264120 KB |
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<deque> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> #include<cassert> #include<time.h> #include<bitset> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; const long long d2=500000004; const double EPS=1e-6; const double PI=acos(-1.0); int ABS(int a){return max(a,-a);} long long ABS(long long a){return max(a,-a);} vector<int>g[110000]; vector<int>rev[110000]; int at[110000][320]; int dist[110000][320]; const int SQ=320; int tmp_a[330]; int tmp_b[330]; int use[110000]; int z[110000]; int dp[110000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<b;i++){ int p,q;scanf("%d%d",&p,&q);p--;q--; g[p].push_back(q); rev[q].push_back(p); } for(int i=0;i<a;i++)for(int j=0;j<320;j++) dist[i][j]=-mod; for(int i=0;i<a;i++){ dist[i][0]=0; at[i][0]=i; } for(int i=0;i<a;i++){ for(int j=0;j<g[i].size();j++){ int to=g[i][j]; int left=0; int right=0; int sz=0; while(left<SQ||right<SQ){ if(sz==SQ)break; int S,T; if((left==SQ||dist[i][left]<0)&&(right==SQ||dist[to][right]<0))break; if(right==SQ||(left<SQ&&dist[i][left]+1>=dist[to][right])){ S=at[i][left]; T=dist[i][left]+1; left++; }else{ S=at[to][right]; T=dist[to][right]; right++; } if(!use[S]){ tmp_a[sz]=S; tmp_b[sz]=T; use[S]=1; sz++; } } for(int k=0;k<sz;k++)dist[to][k]=tmp_b[k]; for(int k=0;k<sz;k++)at[to][k]=tmp_a[k]; for(int k=0;k<sz;k++)use[tmp_a[k]]=0; } } for(int i=0;i<c;i++){ int x,y;scanf("%d%d",&x,&y); x--; for(int j=0;j<y;j++){ scanf("%d",z+j); z[j]--; } for(int j=0;j<y;j++){ use[z[j]]=1; } if(y<SQ){ bool ok=false; for(int j=0;j<SQ;j++){ if(dist[x][j]<0)break; if(!use[at[x][j]]){ ok=true; printf("%d\n",dist[x][j]); break; } } if(!ok)printf("-1\n"); }else{ for(int j=0;j<a;j++){ dp[j]=-mod; } dp[x]=0; for(int j=x;j>=0;j--){ for(int k=0;k<rev[j].size();k++){ dp[rev[j][k]]=max(dp[rev[j][k]],dp[j]+1); } } int ret=-1; for(int j=0;j<a;j++){ if(!use[j])ret=max(ret,dp[j]); } printf("%d\n",ret); } for(int j=0;j<y;j++){ use[z[j]]=0; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5412 KB | Output is correct |
2 | Correct | 7 ms | 5492 KB | Output is correct |
3 | Correct | 8 ms | 5568 KB | Output is correct |
4 | Correct | 7 ms | 5588 KB | Output is correct |
5 | Correct | 13 ms | 8276 KB | Output is correct |
6 | Correct | 12 ms | 8276 KB | Output is correct |
7 | Correct | 13 ms | 8276 KB | Output is correct |
8 | Correct | 15 ms | 8276 KB | Output is correct |
9 | Correct | 17 ms | 8276 KB | Output is correct |
10 | Correct | 14 ms | 8276 KB | Output is correct |
11 | Correct | 15 ms | 8276 KB | Output is correct |
12 | Correct | 8 ms | 8344 KB | Output is correct |
13 | Correct | 15 ms | 8344 KB | Output is correct |
14 | Correct | 15 ms | 8344 KB | Output is correct |
15 | Correct | 14 ms | 8344 KB | Output is correct |
16 | Correct | 11 ms | 8344 KB | Output is correct |
17 | Correct | 15 ms | 8344 KB | Output is correct |
18 | Correct | 14 ms | 8344 KB | Output is correct |
19 | Correct | 13 ms | 8344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5412 KB | Output is correct |
2 | Correct | 7 ms | 5492 KB | Output is correct |
3 | Correct | 8 ms | 5568 KB | Output is correct |
4 | Correct | 7 ms | 5588 KB | Output is correct |
5 | Correct | 13 ms | 8276 KB | Output is correct |
6 | Correct | 12 ms | 8276 KB | Output is correct |
7 | Correct | 13 ms | 8276 KB | Output is correct |
8 | Correct | 15 ms | 8276 KB | Output is correct |
9 | Correct | 17 ms | 8276 KB | Output is correct |
10 | Correct | 14 ms | 8276 KB | Output is correct |
11 | Correct | 15 ms | 8276 KB | Output is correct |
12 | Correct | 8 ms | 8344 KB | Output is correct |
13 | Correct | 15 ms | 8344 KB | Output is correct |
14 | Correct | 15 ms | 8344 KB | Output is correct |
15 | Correct | 14 ms | 8344 KB | Output is correct |
16 | Correct | 11 ms | 8344 KB | Output is correct |
17 | Correct | 15 ms | 8344 KB | Output is correct |
18 | Correct | 14 ms | 8344 KB | Output is correct |
19 | Correct | 13 ms | 8344 KB | Output is correct |
20 | Correct | 696 ms | 10624 KB | Output is correct |
21 | Correct | 637 ms | 10644 KB | Output is correct |
22 | Correct | 684 ms | 10652 KB | Output is correct |
23 | Correct | 860 ms | 10780 KB | Output is correct |
24 | Correct | 1197 ms | 262288 KB | Output is correct |
25 | Correct | 1151 ms | 262412 KB | Output is correct |
26 | Correct | 1085 ms | 262412 KB | Output is correct |
27 | Correct | 861 ms | 263784 KB | Output is correct |
28 | Correct | 995 ms | 263876 KB | Output is correct |
29 | Correct | 952 ms | 263876 KB | Output is correct |
30 | Correct | 917 ms | 263876 KB | Output is correct |
31 | Correct | 983 ms | 263876 KB | Output is correct |
32 | Correct | 973 ms | 263876 KB | Output is correct |
33 | Correct | 746 ms | 263876 KB | Output is correct |
34 | Correct | 843 ms | 263876 KB | Output is correct |
35 | Correct | 822 ms | 263876 KB | Output is correct |
36 | Correct | 902 ms | 263876 KB | Output is correct |
37 | Correct | 865 ms | 263876 KB | Output is correct |
38 | Correct | 916 ms | 263876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5412 KB | Output is correct |
2 | Correct | 7 ms | 5492 KB | Output is correct |
3 | Correct | 8 ms | 5568 KB | Output is correct |
4 | Correct | 7 ms | 5588 KB | Output is correct |
5 | Correct | 13 ms | 8276 KB | Output is correct |
6 | Correct | 12 ms | 8276 KB | Output is correct |
7 | Correct | 13 ms | 8276 KB | Output is correct |
8 | Correct | 15 ms | 8276 KB | Output is correct |
9 | Correct | 17 ms | 8276 KB | Output is correct |
10 | Correct | 14 ms | 8276 KB | Output is correct |
11 | Correct | 15 ms | 8276 KB | Output is correct |
12 | Correct | 8 ms | 8344 KB | Output is correct |
13 | Correct | 15 ms | 8344 KB | Output is correct |
14 | Correct | 15 ms | 8344 KB | Output is correct |
15 | Correct | 14 ms | 8344 KB | Output is correct |
16 | Correct | 11 ms | 8344 KB | Output is correct |
17 | Correct | 15 ms | 8344 KB | Output is correct |
18 | Correct | 14 ms | 8344 KB | Output is correct |
19 | Correct | 13 ms | 8344 KB | Output is correct |
20 | Correct | 696 ms | 10624 KB | Output is correct |
21 | Correct | 637 ms | 10644 KB | Output is correct |
22 | Correct | 684 ms | 10652 KB | Output is correct |
23 | Correct | 860 ms | 10780 KB | Output is correct |
24 | Correct | 1197 ms | 262288 KB | Output is correct |
25 | Correct | 1151 ms | 262412 KB | Output is correct |
26 | Correct | 1085 ms | 262412 KB | Output is correct |
27 | Correct | 861 ms | 263784 KB | Output is correct |
28 | Correct | 995 ms | 263876 KB | Output is correct |
29 | Correct | 952 ms | 263876 KB | Output is correct |
30 | Correct | 917 ms | 263876 KB | Output is correct |
31 | Correct | 983 ms | 263876 KB | Output is correct |
32 | Correct | 973 ms | 263876 KB | Output is correct |
33 | Correct | 746 ms | 263876 KB | Output is correct |
34 | Correct | 843 ms | 263876 KB | Output is correct |
35 | Correct | 822 ms | 263876 KB | Output is correct |
36 | Correct | 902 ms | 263876 KB | Output is correct |
37 | Correct | 865 ms | 263876 KB | Output is correct |
38 | Correct | 916 ms | 263876 KB | Output is correct |
39 | Correct | 1073 ms | 263876 KB | Output is correct |
40 | Correct | 1008 ms | 263876 KB | Output is correct |
41 | Correct | 1032 ms | 263876 KB | Output is correct |
42 | Correct | 1183 ms | 263876 KB | Output is correct |
43 | Correct | 990 ms | 263876 KB | Output is correct |
44 | Correct | 694 ms | 263876 KB | Output is correct |
45 | Correct | 684 ms | 263876 KB | Output is correct |
46 | Correct | 675 ms | 263876 KB | Output is correct |
47 | Correct | 695 ms | 263876 KB | Output is correct |
48 | Correct | 678 ms | 263876 KB | Output is correct |
49 | Correct | 972 ms | 264032 KB | Output is correct |
50 | Correct | 917 ms | 264032 KB | Output is correct |
51 | Correct | 669 ms | 264032 KB | Output is correct |
52 | Correct | 623 ms | 264032 KB | Output is correct |
53 | Correct | 934 ms | 264032 KB | Output is correct |
54 | Correct | 912 ms | 264032 KB | Output is correct |
55 | Correct | 885 ms | 264032 KB | Output is correct |
56 | Correct | 911 ms | 264032 KB | Output is correct |
57 | Correct | 745 ms | 264032 KB | Output is correct |
58 | Correct | 720 ms | 264032 KB | Output is correct |
59 | Correct | 662 ms | 264032 KB | Output is correct |
60 | Correct | 686 ms | 264032 KB | Output is correct |
61 | Correct | 1343 ms | 264032 KB | Output is correct |
62 | Correct | 1210 ms | 264032 KB | Output is correct |
63 | Correct | 1141 ms | 264032 KB | Output is correct |
64 | Correct | 1247 ms | 264032 KB | Output is correct |
65 | Correct | 1429 ms | 264032 KB | Output is correct |
66 | Correct | 1432 ms | 264032 KB | Output is correct |
67 | Correct | 888 ms | 264032 KB | Output is correct |
68 | Correct | 895 ms | 264032 KB | Output is correct |
69 | Correct | 837 ms | 264032 KB | Output is correct |
70 | Correct | 889 ms | 264032 KB | Output is correct |
71 | Correct | 911 ms | 264032 KB | Output is correct |
72 | Correct | 877 ms | 264032 KB | Output is correct |
73 | Correct | 959 ms | 264032 KB | Output is correct |
74 | Correct | 944 ms | 264032 KB | Output is correct |
75 | Correct | 963 ms | 264032 KB | Output is correct |
76 | Correct | 989 ms | 264120 KB | Output is correct |
77 | Correct | 875 ms | 264120 KB | Output is correct |
78 | Correct | 859 ms | 264120 KB | Output is correct |
79 | Correct | 662 ms | 264120 KB | Output is correct |
80 | Correct | 636 ms | 264120 KB | Output is correct |
81 | Correct | 633 ms | 264120 KB | Output is correct |
82 | Correct | 954 ms | 264120 KB | Output is correct |
83 | Correct | 1142 ms | 264120 KB | Output is correct |
84 | Correct | 982 ms | 264120 KB | Output is correct |
85 | Correct | 1016 ms | 264120 KB | Output is correct |
86 | Correct | 895 ms | 264120 KB | Output is correct |
87 | Correct | 943 ms | 264120 KB | Output is correct |
88 | Correct | 718 ms | 264120 KB | Output is correct |
89 | Correct | 703 ms | 264120 KB | Output is correct |
90 | Correct | 676 ms | 264120 KB | Output is correct |
91 | Correct | 711 ms | 264120 KB | Output is correct |
92 | Correct | 663 ms | 264120 KB | Output is correct |
93 | Correct | 667 ms | 264120 KB | Output is correct |
94 | Correct | 933 ms | 264120 KB | Output is correct |
95 | Correct | 825 ms | 264120 KB | Output is correct |
96 | Correct | 839 ms | 264120 KB | Output is correct |
97 | Correct | 777 ms | 264120 KB | Output is correct |
98 | Correct | 767 ms | 264120 KB | Output is correct |
99 | Correct | 763 ms | 264120 KB | Output is correct |
100 | Correct | 937 ms | 264120 KB | Output is correct |
101 | Correct | 924 ms | 264120 KB | Output is correct |
102 | Correct | 873 ms | 264120 KB | Output is correct |
103 | Correct | 886 ms | 264120 KB | Output is correct |
104 | Correct | 868 ms | 264120 KB | Output is correct |
105 | Correct | 858 ms | 264120 KB | Output is correct |
106 | Correct | 1054 ms | 264120 KB | Output is correct |
107 | Correct | 919 ms | 264120 KB | Output is correct |
108 | Correct | 880 ms | 264120 KB | Output is correct |
109 | Correct | 883 ms | 264120 KB | Output is correct |
110 | Correct | 910 ms | 264120 KB | Output is correct |
111 | Correct | 870 ms | 264120 KB | Output is correct |
112 | Correct | 711 ms | 264120 KB | Output is correct |
113 | Correct | 706 ms | 264120 KB | Output is correct |
114 | Correct | 658 ms | 264120 KB | Output is correct |
115 | Correct | 674 ms | 264120 KB | Output is correct |
116 | Correct | 669 ms | 264120 KB | Output is correct |
117 | Correct | 671 ms | 264120 KB | Output is correct |
118 | Correct | 1010 ms | 264120 KB | Output is correct |
119 | Correct | 969 ms | 264120 KB | Output is correct |
120 | Correct | 972 ms | 264120 KB | Output is correct |
121 | Correct | 956 ms | 264120 KB | Output is correct |
122 | Correct | 915 ms | 264120 KB | Output is correct |
123 | Correct | 933 ms | 264120 KB | Output is correct |
124 | Correct | 952 ms | 264120 KB | Output is correct |
125 | Correct | 996 ms | 264120 KB | Output is correct |
126 | Correct | 1000 ms | 264120 KB | Output is correct |