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

你现在查看的是最新测评结果

[2024-12-09 11:08:38]
评测

测评结果：WA
用时：3ms
内存：16792kb

查看

[2024-12-09 11:08:37]
提交

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;
}

源文件, 语言: C++23

详细

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:

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'