oj.uz

Submission #572092

# Submission time Handle Problem Language Result Execution time Memory
572092 2022-06-03T15:34:52 Z YouAreMyGalaxy Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 307 ms 300308 KB 
//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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 197488 KB Output is correct
2 Correct 90 ms 197516 KB Output is correct
3 Correct 94 ms 197560 KB Output is correct
4 Correct 90 ms 197528 KB Output is correct
5 Correct 91 ms 197552 KB Output is correct
6 Correct 102 ms 197684 KB Output is correct
7 Correct 91 ms 197604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 217284 KB Output is correct
2 Correct 143 ms 216720 KB Output is correct
3 Correct 154 ms 215532 KB Output is correct
4 Correct 162 ms 216660 KB Output is correct
5 Correct 210 ms 278000 KB Output is correct
6 Correct 207 ms 276904 KB Output is correct
7 Correct 188 ms 225024 KB Output is correct
8 Correct 278 ms 300308 KB Output is correct
9 Correct 307 ms 292416 KB Output is correct
10 Correct 155 ms 215848 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 199920 KB Output is correct
2 Correct 115 ms 199132 KB Output is correct
3 Correct 110 ms 199484 KB Output is correct
4 Correct 106 ms 199500 KB Output is correct
5 Correct 201 ms 199128 KB Output is correct
6 Correct 219 ms 199396 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 197488 KB Output is correct
2 Correct 90 ms 197516 KB Output is correct
3 Correct 94 ms 197560 KB Output is correct
4 Correct 90 ms 197528 KB Output is correct
5 Correct 91 ms 197552 KB Output is correct
6 Correct 102 ms 197684 KB Output is correct
7 Correct 91 ms 197604 KB Output is correct
8 Correct 141 ms 217284 KB Output is correct
9 Correct 143 ms 216720 KB Output is correct
10 Correct 154 ms 215532 KB Output is correct
11 Correct 162 ms 216660 KB Output is correct
12 Correct 210 ms 278000 KB Output is correct
13 Correct 207 ms 276904 KB Output is correct
14 Correct 188 ms 225024 KB Output is correct
15 Correct 278 ms 300308 KB Output is correct
16 Correct 307 ms 292416 KB Output is correct
17 Correct 155 ms 215848 KB Output is correct
18 Correct 107 ms 199920 KB Output is correct
19 Correct 115 ms 199132 KB Output is correct
20 Correct 110 ms 199484 KB Output is correct
21 Correct 106 ms 199500 KB Output is correct
22 Correct 201 ms 199128 KB Output is correct
23 Correct 219 ms 199396 KB Output is correct
24 Correct 152 ms 213988 KB Output is correct
25 Correct 144 ms 211544 KB Output is correct
26 Correct 149 ms 216872 KB Output is correct
27 Correct 221 ms 214128 KB Output is correct
28 Correct 202 ms 218596 KB Output is correct
29 Correct 150 ms 212168 KB Output is correct