QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#634585	#7039. Counting Failures on a Trie	George_Plover	RE	3ms	20256kb	C++14	4.0kb	2024-10-12 17:40:14	2024-10-12 17:40:15

Judging History

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

[2024-10-12 17:40:15]
评测

测评结果：RE
用时：3ms
内存：20256kb

查看

[2024-10-12 17:40:14]
提交

answer

#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>

#define MAXN 100005
#define LL long long
using namespace std;

int T;
pair<int,int> t[MAXN];

inline LL mul(LL a,LL b,LL MOD){
    a%=MOD;b%=MOD;LL c=(long double) a*b/MOD;
    LL ans = a*b-c*MOD;
    if(ans<0)ans+=MOD; else if(ans>=MOD) ans-=MOD;
    return ans;
}

struct HashValue{
    map<LL,int>US;
    LL power[MAXN];
    LL hash[MAXN];
    LL base;
    LL mod;
    
    void insert(LL x,int y){
        assert(!US.count(x));
        US[x]=y;
    }

    void clear(){
        US.clear();
    }

    int Query(LL x){
        if(!US.count(x))return -1;
        return US[x];
    }

    void init(char *str,LL _base,LL _mod){
        US.clear();
        base = _base;
        mod = _mod;
        int len = strlen(str+1);
        power[0]=1;
        hash[0]=0;
        for(int i=1;i<=len;i++){
            power[i] = mul(power[i-1],(LL)base,mod);
            hash[i] = (mul(hash[i-1],(LL)base,mod)+str[i])%mod;
        }
    }

    LL query(int l,int r){
        return (hash[r]-mul(hash[l-1],power[r-l+1],mod)+mod)%mod;
    }
}h[2];

map<pair<int,int>,int>test;

struct Trie{
    int hv[MAXN][2];
    int fa[18][MAXN];
    int cnt;
    void init(int n){
        cnt = n;
        hv[0][0] = hv[0][1] = 0;
        test.clear();
        for(int i=1;i<=n;i++){
            for(int j=0;j<2;j++){
                hv[i][j] = (mul(hv[t[i].first][j],h[j].base,h[j].mod)+t[i].second+'a')%h[j].mod;
                h[j].insert(hv[i][j],i);
            }
            assert(test.count(t[i])==0);
            test[t[i]]=1;
            fa[0][i] = t[i].first;
        }
        for(int j=1;j<18;j++)
            for(int i=1;i<=n;i++)
                fa[j][i] = fa[j-1][fa[j-1][i]];
    }
    int kth_fa(int x,int k){
        for(int j=0;j<=17 && k;j++){
            if(k&1){
                x = fa[j][x];
            }
            k>>=1;
        }
        return x;
    }
}trie;

int n,m,q;
char str[MAXN];
int f[18][MAXN];
int one_jump[MAXN],end_loc[MAXN];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++){
            int x;char y[5];
            scanf("%d%s",&x,y);
            t[i]=make_pair(x,(int)y[0]-'a');
        }
        scanf("%s",str+1);
        h[0].init(str,277,100055128505716009ll);
        h[1].init(str,367,100055128505716009ll);
        trie.init(n);
        for(int i=1;i<=m;i++){
            int L=i-1,R=m;
            while(L!=R){
                int mid=(L+R+1)/2;
                int loc1 = h[0].Query(h[0].query(i,mid));
                int loc2 = h[1].Query(h[1].query(i,mid));
                if(loc1!=-1 && loc2!=-1 && loc1==loc2){
                    L=mid;
                }
                else{
                    R=mid-1;
                }
            }
            one_jump[i] = R;
            //cout<<R<<" ";
            end_loc[i] = h[0].Query(h[0].query(i,R));

            f[0][i] = ((R+2)>m)?0:(R+2);
            //cout<<f[0][i]<<" ";
        }//cout<<endl;
        //cout<<f[0][3]<<" "<<one_jump[3]<<endl;;
        for(int j=1;j<18;j++){
            for(int i=1;i<=m;i++){
                f[j][i] = f[j-1][f[j-1][i]];
            }
        }
        for(int i=1;i<=q;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            int cnt = 0,loc = 0;
            for(int j=17;j>=0;j--){
                //cout<<f[j][l]<<" "<<j<<endl;
                if(!f[j][l] || f[j][l]>r)continue;
                cnt+=(1<<j);
                l = f[j][l];
                //cout<<l<<" "<<cnt<<" ";
            }//cout<<endl;
            if(one_jump[l]+1==r){
                cnt++;
                loc = 0;
            }
            else{
                loc = trie.kth_fa(end_loc[l],one_jump[l]-r);
            }
            printf("%d %d\n",cnt,loc);
        }
    }
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 20256kb

input:

1
5 10 5
0 a
0 b
1 a
1 c
2 a
aaacbaacab
1 5
1 6
1 7
3 9
4 10

output:

result:

ok 5 lines

Test #2:

score: -100

Runtime Error

input:

1000
1000 1000 1000
0 a
1 a
2 b
3 a
4 b
5 a
6 b
7 b
8 a
9 b
10 b
11 b
12 b
13 b
14 b
15 a
16 a
17 b
18 a
19 a
20 b
21 a
22 b
23 a
24 b
25 a
26 b
27 b
28 b
29 b
30 a
31 b
32 a
33 a
34 a
35 b
36 b
37 b
38 a
39 a
40 b
41 a
42 b
43 a
44 b
45 b
46 a
47 a
48 a
49 a
50 b
51 b
52 a
53 b
54 b
55 a
56 a
57 b
...

output: