F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 5417 >> 求助,为什么在洛谷AC而在bzoj上无故CE?
secretoier @ 2019-01-09 14:05:13
[ Quote ] [ Edit ] [ Delete ] 1#
自己计算了空间是413MB左右,感觉应该没有爆空间。。。那就不知道是为什么会无故CE了。。。
有大佬知道这是为什么吗?
代码:
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(register int x=y; x<=z; x++)
#define downrep(x,y,z) for(register int x=y; x>=z; x--)
#define LL long long
#define repedge(x,y) for(register int x=hed[y]; ~x; x=edge[x].nex)
#define ms(x,y,z) memset(x,y,sizeof(z))
#define lson tr[nod].ch[0]
#define rson tr[nod].ch[1]
#define flson tr[fnod].ch[0]
#define frson tr[fnod].ch[1]
#define lc (nod<<1)
#define rc ((nod<<1)|1)
inline int read(){
int x=0; int w=0; char ch=0;
while(ch<'0' || ch>'9') w|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return w? (-x):x;
}
const int N=1000005;
const int C=26;
const int maxn=10000005;
const int inf=10000005;
int n,m,nedge,hed[N],L,R,nw;
LL num1,num2,ans;
char S[N],T[N];
struct Suffix_Automaton{
int tot,last,root,len[N],fa[N],son[N][C],val[N];
void init(){
rep(i,0,tot){ len[i]=fa[i]=val[i]=0; rep(j,0,C-1) son[i][j]=0; }
tot=0; last=root=++tot;
}
void extend(int i,int c){
int p=last; int np=++tot; last=np;
len[np]=len[p]+1; val[np]=i;
while(p && (!son[p][c])) son[p][c]=np,p=fa[p];
if (!p) fa[np]=root;
else{
int q=son[p][c];
if (len[q]==len[p]+1) fa[np]=q;
else{
int nq=++tot;
fa[nq]=fa[q]; rep(j,0,C-1) son[nq][j]=son[q][j];
len[nq]=len[p]+1; fa[q]=fa[np]=nq;
while(p && (son[p][c]==q)) son[p][c]=nq,p=fa[p];
}
}
}
}sam,sam2;
struct Edge{ int to,nex; }edge[N];
void addedge(int a,int b){
edge[nedge].to=b; edge[nedge].nex=hed[a]; hed[a]=nedge++;
}
struct node{ int ch[2]; LL num; }tr[maxn];
struct Persistable_Segment_Tree{
int L[N],R[N],root[N],tot,cnt;
void pushup(int nod){
tr[nod].num=tr[lson].num+tr[rson].num;
}
void update(int l,int r,int fnod,int &nod,int x){
tr[nod=++cnt]=tr[fnod];
if (l==r){ tr[nod].num+=1ll; return; }
int mid=((l+r)>>1);
if (x<=mid) update(l,mid,flson,lson,x);
else update(mid+1,r,frson,rson,x);
pushup(nod);
}
void dfs(int k){
if (sam.val[k]){
L[k]=R[k]=++tot;
update(1,n,root[tot-1],root[tot],sam.val[k]);
}else L[k]=inf,R[k]=0;
repedge(i,k){
int v=edge[i].to;
dfs(v);
L[k]=min(L[k],L[v]); R[k]=max(R[k],R[v]);
}
}
LL query(int l,int r,int fnod,int nod,int ll,int rr){
if ((l==ll)&&(r==rr)) return tr[nod].num-tr[fnod].num;
int mid=((l+r)>>1);
if (rr<=mid) return query(l,mid,flson,lson,ll,rr);
else if (ll>mid) return query(mid+1,r,frson,rson,ll,rr);
else return query(l,mid,flson,lson,ll,mid)+query(mid+1,r,frson,rson,mid+1,rr);
}
}pseg;
int hf(int k){
if ((L+nw>R)||(pseg.L[k]>pseg.R[k])) return 0;
return pseg.query(1,n,pseg.root[pseg.L[k]-1],pseg.root[pseg.R[k]],L+nw,R);
}
#define repE(x,y) for(int x=head[y]; ~x; x=E[x].nex)
int Nedge,head[N],tmp[N],minr[N];
Edge E[N];
void addE(int a,int b){
E[Nedge].to=b; E[Nedge].nex=head[a]; head[a]=Nedge++;
}
void dfs(int k){
minr[k]=(sam2.val[k])? sam2.val[k]:(m+1);
repE(i,k){
int v=E[i].to;
dfs(v);
minr[k]=min(minr[k],minr[v]);
}
}
int main(){
scanf("%s",&S); sam.init();
n=strlen(S); rep(i,1,n) sam.extend(i,S[i-1]-'a');
nedge=0; ms(hed,-1,hed);
rep(i,1,sam.tot) if (sam.fa[i]) addedge(sam.fa[i],i);
pseg.dfs(sam.root);
int q; scanf("%d",&q);
rep(i,1,q){
scanf("%s",&T); scanf("%d%d",&L,&R);
m=strlen(T);
sam2.init(); rep(j,1,m) sam2.extend(j,T[j-1]-'a');
num2=0; int k=sam.root; nw=0;
rep(j,1,m){
int u=T[j-1]-'a';
for(;;){
if (sam.son[k][u]&&hf(sam.son[k][u])){
k=sam.son[k][u]; ++nw; break;
}
if (nw==0) break;
--nw;
if (nw==sam.len[sam.fa[k]]) k=sam.fa[k];
}
tmp[j]=nw;
}
Nedge=0; rep(j,1,sam2.tot) head[j]=-1;
rep(j,1,sam2.tot) if (sam2.fa[j]) addE(sam2.fa[j],j);
dfs(sam2.root);
ans=0; rep(j,1,sam2.tot) if (j!=sam2.root)
ans+=1ll*max(0,sam2.len[j]-max(sam2.len[sam2.fa[j]],tmp[minr[j]]));
printf("%lld\n",ans);
}
return 0;
}

WAAutoMaton @ 2019-01-18 10:17:46
[ Quote ] [ Edit ] [ Delete ] 2#
struct里面开超大数组会搞挂部分版本的gcc
疑似是gcc的bug
secretoier @ 2019-02-18 21:49:46
[ Quote ] [ Edit ] [ Delete ] 3#
@WAAutoMaton

应该确实是这个的问题……我把结构体里的数组放到外面就AC了
谢谢巨佬qwq
[Top] [Previous Page] [Next Page]

HOME Back