Submission #1258823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258823		Sam_arvandi	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	1380 ms	424600 KiB

selling_rna

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

typedef long long ll;
typedef pair<ll, ll> pii;

#define FOR(i, j, n) for(ll i = j; i<= n; i++)
#define ROF(i, n, j) for(ll i = n; i>= j; i--)
#define pb push_back
#define F first
#define S second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define G(i, j) get<j-1>(i)
#define prll(x) cout << #x << ": " << x << endl;

const ll mn = 1e5 + 5, ms = 2e6 + 5, p = 1e6 + 3, mod = 1e9 + 7, mc = 6;
string a[mn];
pair<string, string> qu[mn];
ll pp[mn], h[mn];
unordered_map<ll, bool> mark;
set<pii> g[ms];
ll ans[mn];

struct Trie
{
        struct Node
        {
                ll c[mc], num;
                vector<ll> k, t;
        }tmp;
        ll n = 0;
        vector<Node> node;

        void add(ll id, ll ind, ll po)
        {
                string s = a[ind];
                if (po == s.size())
                {
                        ll tmp = (p*s[po-1])%mod;
                        if (mark[tmp]) node[id].k.pb(tmp);
                        ROF(i, po-2, 0)
                        {
                                tmp = (tmp*p)%mod;
                                tmp = (tmp+(s[i]*p)%mod)%mod;
                                if (mark[tmp]) node[id].k.pb(tmp);
                        }
                        return;
                }
                if (node[id].c[s[po]-'a'] == 0)
                {
                        n++;
                        node.pb(tmp);
                        node[id].c[s[po]-'a'] = n;
                }
                add(node[id].c[s[po]-'a'], ind, po+1);
        }

        void add2(ll id, ll ind, ll po)
        {
                string s = qu[ind].F;
                if (po == s.size())
                {
                        node[id].t.pb(ind);
                        return;
                }
                if (node[id].c[s[po]-'a'] == 0)
                {
                        return;
                }
                add2(node[id].c[s[po]-'a'], ind, po+1);
        }

        void ezaf(ll id, ll u, ll ted)
        {
                auto it = g[id].lower_bound({u, 0});
                if (it == g[id].end() or (*it).F != u)
                {
                        g[id].insert({u, ted});
                }
                else
                {
                        ted += (*it).S;
                        g[id].erase(it);
                        g[id].insert({u, ted});
                }
                return;
        }
        
        void init(ll id)
        {
                FOR(i, 0, 3)
                {
                        if (node[id].c[i] != 0) init(node[id].c[i]);
                }
                pii maxi = {node[id].k.size(), id};
                FOR(i, 0, 3)
                {
                        if (g[node[node[id].c[i]].num].size() > maxi.F)
                        {
                                maxi = {g[node[node[id].c[i]].num].size(), node[node[id].c[i]].num};
                        }
                }
                node[id].num = maxi.S;
                for(auto u: node[id].k)
                {
                        ezaf(node[id].num, u, 1);
                }
                FOR(i, 0, 3)
                {
                        if (node[id].c[i] != 0 and node[node[id].c[i]].num != node[id].num)
                        {
                                auto it = g[node[node[id].c[i]].num].begin();
                                while (it != g[node[node[id].c[i]].num].end())
                                {
                                        ezaf(node[id].num, (*it).F, (*it).S);
                                        it++;
                                }
                        }
                }
                for(auto ind: node[id].t)
                {
                        ll u = h[ind];
                        auto it = g[node[id].num].lower_bound({u, 0});
                        if (it == g[node[id].num].end() or (*it).F != u) continue;
                        ans[ind] = (*it).S;
                }
        }

}tr;

ll get_hash(string s)
{
        ll tmp = 0;
        FOR(i, 0, s.size()-1)
        {
                tmp = (tmp+(pp[i+1]*s[i])%mod)%mod;
        }
        return tmp;
}

signed main()
{
        IOS;
        tr.node.pb(tr.tmp);
        ll n, q;
        cin >> n >> q;

        pp[0] = 1;
        FOR(i, 1, max(n, q))
        {
                pp[i] = (pp[i-1]*p)%mod;
        }

        FOR(i, 1, n)
        {
                cin >> a[i];
                FOR(j, 0, a[i].size()-1)
                {
                        if (a[i][j] == 'A') a[i][j] = 'a';
                        if (a[i][j] == 'U') a[i][j] = 'b';
                        if (a[i][j] == 'G') a[i][j] = 'c';
                        if (a[i][j] == 'C') a[i][j] = 'd';
                }
        }
        FOR(i, 1, q)
        {
                string s1, s2;
                cin >> s1 >> s2;
                FOR(j, 0, s1.size()-1)
                {
                        if (s1[j] == 'A') s1[j] = 'a';
                        if (s1[j] == 'U') s1[j] = 'b';
                        if (s1[j] == 'G') s1[j] = 'c';
                        if (s1[j] == 'C') s1[j] = 'd';
                }
                FOR(j, 0, s2.size()-1)
                {
                        if (s2[j] == 'A') s2[j] = 'a';
                        if (s2[j] == 'U') s2[j] = 'b';
                        if (s2[j] == 'G') s2[j] = 'c';
                        if (s2[j] == 'C') s2[j] = 'd';
                }
                qu[i] = {s1, s2};
                h[i] = get_hash(s2);
                mark[h[i]] = 1;
        }
        FOR(i,1 , n)
        {
                tr.add(0, i, 0);
        }
        FOR(i, 1, q)
        {
                tr.add2(0, i, 0);
        }
        tr.init(0);
        FOR(i,1 , q)
        {
                cout << ans[i] << "\n";
        }
        return 0;
}

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