QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#806498 | #7188. Aho-Corasick Automaton | Zi_Gao | WA | 3ms | 16792kb | C++23 | 5.0kb | 2024-12-09 11:08:37 | 2024-12-09 11:08:38 |
Judging History
answer
#include<bits/stdc++.h>
struct IO{static const int inSZ=1<<17;char inBuf[inSZ],*in1,*in2;template<class T>inline __attribute((always_inline))T read(){if(in1>inBuf+inSZ-32)[[unlikely]]{auto len=in2-in1;memcpy(inBuf,in1,len);in1=inBuf,in2=inBuf+len;in2+=fread(in2,1,inSZ-len,stdin);if(in2!=inBuf+inSZ)*in2=0;}T res=0;unsigned char c;bool neg=0;while((c=*in1++)<48)neg=c==45;while(res=res*10+(c-48),(c=*in1++)>=48);return neg?-res:res;}inline __attribute((always_inline))char readCh(){if(in1>inBuf+inSZ-32)[[unlikely]]{auto len=in2-in1;memcpy(inBuf,in1,len);in1=inBuf,in2=inBuf+len;in2+=fread(in2,1,inSZ-len,stdin);if(in2!=inBuf+inSZ)*in2=0;}return*in1++;}static const int outSZ=1<<21;char outBuf[outSZ],*out;template<class T>inline __attribute((always_inline))void write(T x){if(out>outBuf+outSZ-32)[[unlikely]]fwrite(outBuf,1,out-outBuf,stdout),out=outBuf;if(!x)return*out++=48,void();if(x<0)*out++=45,x=-x;alignas(8)const char*digits="0001020304050607080910111213141516171819""2021222324252627282930313233343536373839""4041424344454647484950515253545556575859""6061626364656667686970717273747576777879""8081828384858687888990919293949596979899";alignas(64)static char buf[20];char*p=buf+20;while(x>=10)memcpy(p-=2,digits+x%100*2,2),x/=100;if(x)*--p=48+x;auto len=buf+20-p;memcpy(out,p,len),out+=len;}inline __attribute((always_inline))void printCh(char c){if(out>outBuf+outSZ-32)[[unlikely]]fwrite(outBuf,1,out-outBuf,stdout),out=outBuf;*out++=c;}void init(){in1=in2=inBuf+inSZ;out=outBuf;}~IO(){fwrite(outBuf,1,out-outBuf,stdout);}}IO;template<class T=int>inline T read(){return IO.read<T>();}template<class...Args>inline void read(Args&...args){((args=IO.read<Args>()),...);}template<class T>inline void print(T x,char c){IO.write(x),*IO.out++=c;}template<class T>inline void print(T x){IO.write(x);}inline __attribute((always_inline))void printCh(char c){return IO.printCh(c);}inline __attribute((always_inline))char readCh(){return IO.readCh();}
#define lc (tree[(p)].lChild)
#define rc (tree[(p)].rChild)
#define int int
const int PSEG_DATA_SIZE=200010;
const int PSEG_SIZE=PSEG_DATA_SIZE*25;
struct PSEGTREE_NODE{
int data;
int lChild,rChild;
};
struct PSEGTREE{
PSEGTREE_NODE tree[PSEG_SIZE];
int root[PSEG_SIZE],tot,L,R;
inline __attribute((always_inline)) int getMem(){
return tot++;
}
int build_(int l,int r){
int p=getMem();
if(l==r) tree[p].data=0;
else{
int mid=(l+r)>>1;
tree[p].lChild=build_(l,mid);
tree[p].rChild=build_(mid+1,r);
}
return p;
}
inline __attribute((always_inline)) int query(int p,int pos,int l,int r){
while(l!=r&&p){
int mid=(l+r)>>1;
if(pos<=mid) r=mid,p=tree[p].lChild;
else l=mid+1,p=tree[p].rChild;
}
return tree[p].data;
}
int update(int old,int pos,int l,int r,int c){
int p=getMem();
tree[p]=tree[old];
if(l==r) tree[p].data=c;
else{
int mid=(l+r)>>1;
if(pos<=mid) tree[p].lChild=update(tree[p].lChild,pos,l,mid,c);
else tree[p].rChild=update(tree[p].rChild,pos,mid+1,r,c);
}
return p;
}
inline __attribute((always_inline)) void build(int l,int r){
root[1]=getMem();
}
inline __attribute((always_inline)) int query(int ver,int pos){
return query(root[ver],pos,L,R);
}
inline __attribute((always_inline)) void modify(int old,int ver,int pos,int c){
root[ver]=update(root[old],pos,L,R,c);
return;
}
}pseg;
int n;
struct NODE{
int to,c;
};
struct AC{
std::vector<NODE> mp[200010];
int vis[200010],fail[200010],from[200010];
int cnt=0;
inline __attribute((always_inline)) void addCur(int u){
pseg.root[u]=pseg.root[fail[u]];
for(auto [s,v]:mp[u]){
pseg.modify(u,u,s,v);
}
}
inline __attribute((always_inline)) void build(){
register int u,w;
pseg.build(1,n);
fail[0]=0;
std::queue<int> Q;
for(auto [_,v]:mp[0]){
fail[v]=0;
Q.push(v);
}
addCur(0);
while(!Q.empty()){
u=Q.front(),Q.pop();
// printf("b u%d from%d fail%d\n",u,from[u],fail[u]);
addCur(u);
for(auto [s,v]:mp[u]){
fail[v]=pseg.query(fail[u],s);
Q.push(v);
}
}
}
inline __attribute((always_inline)) int go(int p,int s){return pseg.query(p,s);}
}ac;
int par[200010];
int main(){
#ifndef ONLINE_JUDGE
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
#endif
IO.init();
register int i,c;
n=read();
for(i=1;i<=n;++i) par[i]=read();
for(i=1;i<=n;++i){
ac.mp[par[i]].push_back({read(),i});
}
ac.build();
for(i=1;i<=n;++i) print(ac.fail[i]),printCh(' ');
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 15928kb
input:
2 0 0 1 2
output:
0 0
result:
ok 2 number(s): "0 0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 15788kb
input:
2 0 1 1 1
output:
0 1
result:
ok 2 number(s): "0 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 16608kb
input:
1 0 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 16792kb
input:
50 0 1 1 1 0 0 4 4 3 7 1 11 1 11 2 15 13 11 4 11 5 7 22 17 4 19 19 26 19 27 3 17 9 4 14 8 15 33 33 33 9 40 24 18 5 28 10 1 47 25 20 20 31 1 43 3 3 21 3 3 3 22 43 3 1 20 3 43 43 20 3 20 1 3 20 20 3 1 43 3 20 20 20 29 3 3 3 3 20 1 3 3 3 3 20 3 3 25 3 1
output:
0 6 6 6 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
result:
wrong answer 2nd numbers differ - expected: '1', found: '6'