Submission #572092

#	Time	Username	Problem	Language	Result	Execution time	Memory
572092		YouAreMyGalaxy	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	307 ms	300308 KiB

selling_rna

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5, block = 330, M = 2e6;
vector<int> pre[M + 1], suf[M + 1], adj[M + 1], ans[M + 1];
bool built[M + 1];
bitset<N + 1> visited;
struct Trie
{
    struct node
    {
        int child[26];
        node()
        {
            memset(child, -1, sizeof(child));
        }
    };
    vector<node> tree;
    void new_node()
    {
        node tmp;
        tree.push_back(tmp);
    }
    void reset()
    {
        tree.clear();
        new_node();
    }
    int add_query(string &s)
    {
        int id = 0;
        for (char c : s)
        {
            int w = c - 'A';
            if (tree[id].child[w] == -1)
            {
                tree[id].child[w] = tree.size();
                new_node();
            }
            id = tree[id].child[w];
        }
        return id;
    }
    void add_pattern(int i, int t, string &s)
    {
        int id = 0;
        for (char c : s)
        {
            int w = c - 'A';
            if (tree[id].child[w] == -1)
            {
                return ;
            }
            id = tree[id].child[w];
            if (t)
            {
                suf[id].push_back(i);
            }
            else
            {
                pre[id].push_back(i);
            }
        }
    }
} tree;
void build(int u)
{
    built[u] = true;
    visited.reset();
    sort(adj[u].begin(), adj[u].end());
    adj[u].erase(unique(adj[u].begin(), adj[u].end()), adj[u].end());
    for (int i : pre[u])
    {
        visited[i] = true;
    }
    for (int v : adj[u])
    {
        int res = 0;
        for (int i : suf[v])
        {
            res += visited[i];
        }
        ans[u].push_back(res);
    }
}
string s[N + 1], p[N + 1], q[N + 1];
int n, m, a[N + 1], b[N + 1];
void read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
    }
    for (int i = 1; i <= m; ++ i)
    {
        cin >> p[i] >> q[i];
    }
}
void solve()
{
    tree.reset();
    for (int i = 1; i <= m; ++ i)
    {
        a[i] = tree.add_query(p[i]);
        //cerr << a[i] << '\n';
    }
    for (int i = 1; i <= n; ++ i)
    {
        tree.add_pattern(i, 0, s[i]);
        reverse(s[i].begin(), s[i].end());
    }
    tree.reset();
    for (int i = 1; i <= m; ++ i)
    {
        reverse(q[i].begin(), q[i].end());
        b[i] = tree.add_query(q[i]);
    }
    for (int i = 1; i <= n; ++ i)
    {
        tree.add_pattern(i, 1, s[i]);
    }
    for (int i = 1; i <= m; ++ i)
    {
        adj[a[i]].push_back(b[i]);
        //cerr << a[i] << ' ' << b[i] << '\n';
    }
    for (int i = 1; i <= m; ++ i)
    {
        if (pre[a[i]].size() <= block)
        {
            int res = 0;
            for (int u : pre[a[i]])
            {
                res += binary_search(suf[b[i]].begin(), suf[b[i]].end(), u);
            }
            cout << res << '\n';
        }
        else
        {
            if (!built[a[i]])
            {
                build(a[i]);
            }
            int j = lower_bound(adj[a[i]].begin(), adj[a[i]].end(), b[i]) - adj[a[i]].begin();
            cout << ans[a[i]][j] << '\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case #" << __ << ":" << '\n';
        read();
        solve();
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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