Submission #1160906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160906		Der_Vlapos	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	791 ms	1114112 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

struct BOR
{
    struct Node
    {
        vector<Node *> link;
        vector<string> fin;
        vector<int> qrId;
        int cnt = 0;

        Node()
        {
            link.resize(30, NULL);
        }
    };
    Node *root = new Node();
    int cntNodes = 1;

    BOR() {};

    void add(string s, bool f)
    {
        Node *v = root;
        v->cnt++;
        for (char c : s)
        {
            if (v->link[c - 'a'] == NULL)
            {
                v->link[c - 'a'] = new Node();
                cntNodes++;
            }
            v = v->link[c - 'a'];
            v->cnt++;
        }
        if (f)
        {
            reverse(all(s));
            v->fin.pb(s);
        }
    }

    int getAns(string s)
    {
        Node *v = root;
        for (char c : s)
        {
            if (v != NULL)
                v = v->link[c - 'a'];
        }
        return v == NULL ? 0 : v->cnt;
    }

    void merge(Node *&v, Node *rt)
    {
        if (!rt)
            return;
        if (!v)
        {
            cntNodes++;
            v = new Node();
        }
        v->cnt += rt->cnt;
        for (int i = 0; i < 5; ++i)
            merge(v->link[i], rt->link[i]);
    }

    void merge(BOR &tree)
    {
        if (tree.cntNodes > cntNodes)
            swap(root, tree.root);

        merge(root, tree.root);
    }

    void addQ(string s, int id)
    {
        Node *v = root;
        for (char c : s)
        {
            if (v != NULL)
                v = v->link[c - 'a'];
        }
        if (v != NULL)
            v->qrId.pb(id);
    }

    BOR traverse(Node *v, vector<int> &ans, vector<string> &Qends)
    {
        if (v == NULL)
            return BOR();
        BOR cur;
        for (auto s : v->fin)
            cur.add(s, 0);

        for (int i = 0; i < 5; ++i)
        {
            auto to = traverse(v->link[i], ans, Qends);
            cur.merge(to);
        }

        for (int curId : v->qrId)
        {
            ans[curId] = cur.getAns(Qends[curId]);
        }
        return cur;
    }
};

struct test
{
    map<char, char> letter;

    void solve()
    {
        int n, q;
        cin >> n >> q;
        BOR tree1;
        letter['A'] = 'a';
        letter['G'] = 'b';
        letter['C'] = 'c';
        letter['U'] = 'd';

        auto transform = [&](string &s)
        {
            for (auto &c : s)
                c = letter[c];
        };

        for (int i = 0; i < n; ++i)
        {
            string s;
            cin >> s;
            transform(s);
            tree1.add(s, 1);
        }

        vector<string> ends;
        for (int i = 0; i < q; ++i)
        {
            string st, en;
            cin >> st >> en;

            transform(st);
            transform(en);
            reverse(all(en));

            tree1.addQ(st, i);
            ends.pb(en);
        }

        vector<int> ans(q);

        tree1.traverse(tree1.root, ans, ends);

        for (auto el : ans)
            cout << el << "\n";
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

selling_rna.cpp:170:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  170 | main()
      | ^~~~

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