Submission #1130236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130236		minahttoe	Selling RNA Strands (JOI16_selling_rna)	C++20	Compilation error	0 ms	0 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct node{
    int child[30][30];
    int cnt;
} trie[2000005];

char rna[4]={'A','G','C','U'};
string p,q,s[2000005];
int nnode,n,m,a,b;

int new_node(){
    nnode++;
    memset(trie[nnode].child, -1, sizeof trie[nnode].child);
    trie[nnode].cnt=0;
    return nnode;
}

void ins(string s){
    int cur=0;
    int n=s.size();
    for(int i=0; i<n; i++){
        int c1=s[i]-'A';
        int c2=s[n-i-1]-'A';
        if(trie[cur].child[c1][c2]==-1) trie[cur].child[c1][c2]=new_node();
        cur=trie[cur].child[c1][c2];
        trie[cur].cnt++;
    }
}

int dfs1(int u, int k){
    int ret=0;
    if(k==a-1) return trie[u].cnt;
    for(int i=0; i<4; i++){
        if(trie[u].child[p[k+1]-'A'][rna[i]-'A']!=-1)
            ret+=dfs1(trie[u].child[p[k+1]-'A'][rna[i]-'A'],k+1);
    }
    return ret;
}

int dfs2(int u, int k){
    int ret=0;
    if(k==b-1) return trie[u].cnt;
    for(int i=0; i<4; i++){
        if(trie[u].child[rna[i]-'A'][q[b-k-2]-'A']!=-1)
            ret+=dfs2(trie[u].child[rna[i]-'A'][q[b-k-2]-'A'],k+1);
    }
    return ret;
}

int solve(){
    int cur=0;
    for(int i=0; i<min(a,b); i++){
        int c1=p[i]-'A';
        int c2=q[b-i-1]-'A';
        if(trie[cur].child[c1][c2]==-1) return 0;
        cur=trie[cur].child[c1][c2];
    }
    if(a>b){
        int tmp=dfs1(cur,b-1);
        return tmp;
    }
    if(a<b){
        int tmp=dfs2(cur,a-1);
        return tmp;
    }
    return trie[cur].cnt;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    memset(trie[0].child, -1, sizeof(trie[0].child));
    trie[0].cnt=0;
    for(int i=1; i<=n; i++){
        cin>>s[i];
        ins(s[i]);
    }
    while(m--){
        cin>>p>>q;
        a=p.size(),b=q.size();
        cout<<solve()<<'\n';
    }
    return 0;
}

Compilation message (stderr)

/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xd4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xdb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe2): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
collect2: error: ld returned 1 exit status