这题有谁用AC自动机卡过的吗?
查看原帖
这题有谁用AC自动机卡过的吗?
36532
localhost楼主2020/5/8 01:37

我感觉我已经卡不下去了,fread什么的都上了还是不行

有大佬帮忙卡一卡的吗?

#include<bits/stdc++.h>
#include<bits/extc++.h>
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
#define fur(i,x,y) for(int i=x;i<=y;++i)
const int N=100001;
using std::list,__gnu_pbds::gp_hash_table;
int fail[N],sz,q[N],ans[N],ANS[N],vi[N],VI[N],vp,VP;
list<int>s1[50001],s2[50001],ed[N];
gp_hash_table<int,int>c[N];
bool vis[N],VIS[N];
int main(){
    int n,m,tot,now,v;
    in(n,m);
    fur(i,1,n){
        in(tot);while(tot--)in(v),s1[i].push_back(v);
        in(tot);while(tot--)in(v),s2[i].push_back(v);
    }
    fur(i,1,m){
        now=0,in(tot);
        while(tot--){
            in(v);
            if(!c[now][v])c[now][v]=++sz;
            now=c[now][v];
        }
        ed[now].push_back(i);
    }
    int h=0,t=0;
    for(auto to:c[0])
        fail[to.second]=0,q[t++]=to.second;
    while(h<t){
        int now=q[h++];
        for(auto to:c[now]){
            int k=fail[now];
            while(k&&!c[k][to.first])k=fail[k];
            fail[to.second]=c[k][to.first],q[t++]=to.second;
        }
    }
    fur(i,1,n){
        now=0;
        for(auto x:s1[i]){
            while(now&&!c[now][x])now=fail[now];
            now=c[now][x];
            for(t=now;t;t=fail[t])if(!vis[t]){
                vis[t]=1,vi[++vp]=t;
                for(int to:ed[t])if(!VIS[to])
                    VIS[to]=1,VI[++VP]=to,
                    ++ans[to],++ANS[i];
            }
        }
        now=0;
        for(auto x:s2[i]){
            while(now&&!c[now][x])now=fail[now];
            now=c[now][x];
            for(t=now;t;t=fail[t])if(!vis[t]){
                vis[t]=1,vi[++vp]=t;
                for(int to:ed[t])if(!VIS[to])
                    VIS[to]=1,VI[++VP]=to,
                    ++ans[to],++ANS[i];
            }
        }
        while(vp)vis[vi[vp--]]=0;
        while(VP)VIS[VI[VP--]]=0;
    }
    fur(i,1,m)out(ans[i]),pt('\n');
    fur(i,1,n)out(ANS[i]),pt(' ');
    flush();
}
2020/5/8 01:37
加载中...