洛谷 2922 BZOJ 1590 [USACO08DEC]秘密消息Secret Message

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 #define rg register
 6 #define N 500010
 7 using namespace std;
 8 int n,m,a[N][4],now,ans,tot;
 9 inline int read(){
10     int k=0,f=1; char c=getchar();
11     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
12     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
13     return k*f;
14 }
15 int main(){
16     memset(a,0,sizeof(a)); 
17     n=read(); m=read();
18     for(rg int i=1;i<=n;i++){
19         int x=read(); now=0;
20         while(x--){
21             int y=read();
22             if(a[now][y]>0) now=a[now][y];
23             else a[now][y]=++tot,now=a[now][y];
24             a[now][2]++;
25         }
26         a[now][3]++; 
27     }
28     while(m--){
29         int x=read(); bool ok=1; ans=now=0;
30         while(x--){
31             int y=read();
32             if(a[now][y]&&ok){
33                 now=a[now][y];
34                 if(a[now][3]) ans+=a[now][3];
35             }
36             else ok=0;
37         }
38         if(ok) ans+=a[now][2]-a[now][3];
39         printf("%d\n",ans);
40     } 
41     return 0;
42 }