제출 #1276627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276627		k12_khoi	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1086 ms	464760 KiB

selling_rna

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

const int N=1e5+5;
const int MMM=2e6+5;

int n,request,res;
string P;
string s[N];

namespace sub4
{
    const int root=0;

    struct Node
    {
        int cnt,nxt[26];

        Node()
        {
            cnt=0;
            memset(nxt,-1,sizeof(nxt));
        }
    };
    vector <Node> trie,Rev_trie;

    int save;
    int sz[MMM],hld[MMM],ans[N];
    string Q[N];
    vector <int> add[MMM],query[MMM];

    void init(string &s,int id,int pos)
    {
        sz[id]++;
        trie[id].cnt++;
        if (pos==s.size())
        {
            add[id].emplace_back(save);
            return;
        }

        char c=s[pos]-'A';
        if (trie[id].nxt[c]==-1)
        {
            trie[id].nxt[c]=trie.size();
            trie.emplace_back(Node());
        }

        init(s,trie[id].nxt[c],pos+1);

        if (hld[id]==0 or sz[hld[id]]<sz[trie[id].nxt[c]])
            hld[id]=trie[id].nxt[c];
    }

    void add_queries(string &s,int id,int pos)
    {
        if (pos==s.size())
        {
            query[id].push_back(save);
            return;
        }

        char c=s[pos]-'A';
        if (trie[id].nxt[c]==-1) return;

        add_queries(s,trie[id].nxt[c],pos+1);
    }

    void update_Revstring(string &s,int id,int pos,int neg)
    {
        Rev_trie[id].cnt+=neg;
        if (pos<0) return;

        char c=s[pos]-'A';
        if (Rev_trie[id].nxt[c]==-1)
        {
            Rev_trie[id].nxt[c]=Rev_trie.size();
            Rev_trie.emplace_back(Node());
        }

        update_Revstring(s,Rev_trie[id].nxt[c],pos-1,neg);
    }

    void Update_backstring(int id,int neg)
    {
        for (int j=0;j<26;j++)
        if (trie[id].nxt[j]!=-1) Update_backstring(trie[id].nxt[j],neg);

        for (int j:add[id])
        update_Revstring(s[j],root,s[j].size()-1,neg);
    }

    int Get_revstring(string &s,int id,int pos)
    {
        if (pos<0) return Rev_trie[id].cnt;

        char c=s[pos]-'A';
        if (Rev_trie[id].nxt[c]==-1) return 0;

        return Get_revstring(s,Rev_trie[id].nxt[c],pos-1);
    }

    void solve(int id)
    {
        if (hld[id]!=0)
        {
            for (int j=0;j<26;j++)
            if (trie[id].nxt[j]!=-1 and trie[id].nxt[j]!=hld[id])
            {
                solve(trie[id].nxt[j]);
                Update_backstring(trie[id].nxt[j],-1);
            }

            solve(hld[id]);


            for (int j=0;j<26;j++)
            if (trie[id].nxt[j]!=-1 and trie[id].nxt[j]!=hld[id])
                Update_backstring(trie[id].nxt[j],1);
        }

        for (int j:add[id])
        update_Revstring(s[j],root,s[j].size()-1,1);

        for (int j:query[id])
        ans[j]=Get_revstring(Q[j],root,Q[j].size()-1);
    }

    void solve()
    {
        trie.emplace_back(Node());
        Rev_trie.emplace_back(Node());

        for (int i=1;i<=n;i++)
        {
            save=i;
            init(s[i],root,0);
        }

        for (int i=1;i<=request;i++)
        {
            cin >> P >> Q[i];

            save=i;
            add_queries(P,root,0);
        }

        solve(root);

        for (int i=1;i<=request;i++)
        cout << ans[i] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> request;
    for (int i=1;i<=n;i++)
    cin >> s[i];

    sub4::solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40