Submission #1160913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160913		Der_Vlapos	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	843 ms	351232 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 Node
{
    vector<Node *> link;
    vector<int> fin;
    vector<int> qrId;
    int cnt = 0;
    int cntNodes = 0;

    Node()
    {
        link.resize(5, NULL);
    }
};

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

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

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

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

Node *traverse(Node *v, vector<int> &ans, vector<string> &Qends, vector<string> &strs)
{
    if (v == NULL)
        return NULL;
    Node *curRt = new Node();
    for (auto s : v->fin)
        add(curRt, strs[s], 0, -1);

    for (int i = 0; i < 5; ++i)
    {
        auto to = traverse(v->link[i], ans, Qends, strs);
        if (to)
        {
            if (to->cntNodes > curRt->cntNodes)
                swap(curRt, to);
            int added = merge(curRt, to);
            assert(added <= min(curRt->cntNodes, to->cntNodes));
            curRt->cntNodes += added;
        }
    }

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

struct test
{
    map<char, char> letter;

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

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

        Node *root = new Node();

        vector<string> ends, strs;
        for (int i = 0; i < n; ++i)
        {
            string s;
            cin >> s;
            transform(s);
            add(root, s, 1, i);
            reverse(all(s));
            strs.pb(s);
        }

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

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

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

        vector<int> ans(q);

        traverse(root, ans, ends, strs);

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

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

Compilation message (stderr)

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

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