Submission #732061

#	Time	Username	Problem	Language	Result	Execution time	Memory
732061		bgnbvnbv	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	535 ms	251172 KiB

selling_rna

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll val[300];
struct TrieNode
{
    int child[4];
    int sz;
    int bigchild;
    vector<int>id,query;
    TrieNode()
    {
        for(int j=0;j<4;j++) child[j]=0;
        sz=0;
        bigchild=0;
    }
};
string s[maxN],a[maxN],b[maxN];
struct Trieu
{
    vector<TrieNode>trie;
    void kt()
    {
        trie.pb(TrieNode());
    }
    void add(int j)
    {
        ll p=0;
        for(int i=0;i<s[j].size();i++)
        {
            int nxt=val[s[j][i]];
            if(trie[p].child[nxt]==0)
            {
                trie[p].child[nxt]=trie.size();
                trie.pb(TrieNode());
            }
            p=trie[p].child[nxt];
            trie[p].sz++;
        }
    }
    void ers(int j)
    {
        ll p=0;
        for(int i=0;i<=s[j].size()-1;i++)
        {
            int nxt=val[s[j][i]];
            if(trie[p].child[nxt]==0)
            {
                trie[p].child[nxt]=trie.size();
                trie.pb(TrieNode());
            }
            p=trie[p].child[nxt];
            trie[p].sz--;
        }
    }
    int query(int j)
    {
        ll p=0;
        for(int i=0;i<=a[j].size()-1;i++)
        {
            int nxt=val[a[j][i]];
            if(trie[p].child[nxt]==0)
            {
                trie[p].child[nxt]=trie.size();
                trie.pb(TrieNode());
            }
            p=trie[p].child[nxt];
        }
        return trie[p].sz;
    }
}trieu;ll ans[maxN];
struct Triev
{
    vector<TrieNode>trie;
    void kt()
    {
        trie.pb(TrieNode());
    }
    void add(int j)
    {
        ll p=0;
        for(int i=s[j].size()-1;i>=0;i--)
        {
            int nxt=val[s[j][i]];
            if(trie[p].child[nxt]==0)
            {
                trie[p].child[nxt]=trie.size();
                trie.pb(TrieNode());
            }
            p=trie[p].child[nxt];
        }
        trie[p].id.push_back(j);
        trie[p].sz+=s[j].size();
    }
    void addq(int j)
    {
        ll p=0;
        for(int i=b[j].size()-1;i>=0;i--)
        {
            int nxt=val[b[j][i]];
            if(trie[p].child[nxt]==0)
            {
                trie[p].child[nxt]=trie.size();
                trie.pb(TrieNode());
            }
            p=trie[p].child[nxt];
        }
        trie[p].query.push_back(j);
    }
    void dfs_sz(int u=0)
    {
        trie[u].bigchild=-1;
        for(int i=0;i<4;i++)
        {
            int v=trie[u].child[i];
            if(v!=0)
            {
                dfs_sz(v);
                trie[u].sz+=trie[v].sz;
                int &x=trie[u].bigchild;
                if(x==-1||trie[v].sz>trie[x].sz)
                {
                    x=v;
                }
            }
        }
    }
    void dfs(int u=0,bool keep=1)
    {
        for(int i=0;i<4;i++)
        {
            int v=trie[u].child[i];
            if(v!=0&&v!=trie[u].bigchild)
            {
                dfs(v,0);
            }
        }

        if(trie[u].bigchild!=-1)
        {
            dfs(trie[u].bigchild,1);
            int x=trie[u].bigchild;
            swap(trie[u].id,trie[x].id);
            for(auto zz:trie[x].id) {trie[u].id.pb(zz),trieu.add(zz);}
        }
        else
        {
            for(auto zz:trie[u].id)
            {
                trieu.add(zz);
            }
        }
        for(int i=0;i<4;i++)
        {
            int v=trie[u].child[i];
            if(v!=0&&v!=trie[u].bigchild)
            {
                for(auto zz:trie[v].id)
                {
                    trie[u].id.pb(zz);
                    trieu.add(zz);
                }
            }
        }

        for(auto zz:trie[u].query)
        {
            ans[zz]=trieu.query(zz);
            //if(u==2) cout << zz<<' ';
        }
        if(keep==0)
        {
            for(auto zz:trie[u].id) trieu.ers(zz);
        }
    }
}trie2;
ll n,m;
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> s[i];
    val['A']=0;
    val['U']=1;
    val['G']=2;
    val['C']=3;
    trieu.kt();
    trie2.kt();
    for(int i=1;i<=m;i++)
    {
        cin >> a[i] >> b[i];
    }
    for(int i=1;i<=n;i++)
    {
        trie2.add(i);
    }
    for(int i=1;i<=m;i++)
    {
        trie2.addq(i);
    }
    trie2.dfs_sz();
    trie2.dfs();
    for(int i=1;i<=m;i++) cout << ans[i]<<'\n';
}
int main()
{
    //fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trieu::add(int)':
selling_rna.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0;i<s[j].size();i++)
      |                     ~^~~~~~~~~~~~
selling_rna.cpp:40:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |             int nxt=val[s[j][i]];
      |                                ^
selling_rna.cpp: In member function 'void Trieu::ers(int)':
selling_rna.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0;i<=s[j].size()-1;i++)
      |                     ~^~~~~~~~~~~~~~~
selling_rna.cpp:55:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |             int nxt=val[s[j][i]];
      |                                ^
selling_rna.cpp: In member function 'int Trieu::query(int)':
selling_rna.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i=0;i<=a[j].size()-1;i++)
      |                     ~^~~~~~~~~~~~~~~
selling_rna.cpp:70:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |             int nxt=val[a[j][i]];
      |                                ^
selling_rna.cpp: In member function 'void Triev::add(int)':
selling_rna.cpp:93:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |             int nxt=val[s[j][i]];
      |                                ^
selling_rna.cpp: In member function 'void Triev::addq(int)':
selling_rna.cpp:109:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  109 |             int nxt=val[b[j][i]];
      |                                ^

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