oj.uz

Submission #1048161

# Submission time Handle Problem Language Result Execution time Memory
1048161 2024-08-08T03:26:51 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 63 ms 183632 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second

const int ar = 1e5 + 5;
const int N = 2e6;
int n, m;
string s[ar], r[ar];
string p[ar], q[ar];
const int NUMBEROFNODES = 4 * 100000 + 5;
void remake(string &s)
{
    for (auto &u : s)
    {
        if (u == 'C') u = 'a';
        else if (u == 'U') u = 'b';
        else if (u == 'G') u = 'c';
        else u = 'd';
    }
}
int make[N + 5];
struct Trie{
    int timedfs = 0;
    struct Node{
        int child[5];
        int exist, cnt;
        int id;
        int in, out;
    } nodes[NUMBEROFNODES];

    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].exist = nodes[0].cnt = 0;
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].exist = nodes[cur].cnt = 0;
        return cur;
    }

    void add_string(string &s, int p, bool t) {
        int pos = 0;
        for (auto f : s) {
            int c = f - 'a';
            if (nodes[pos].child[c] == -1){
                nodes[pos].child[c] = new_node();
            }
            pos = nodes[pos].child[c];
            nodes[pos].cnt++;

        }
        nodes[pos].exist++;
        nodes[pos].id =  p;
        if (t) make[p] = pos;
    }

    pair<int, int> find(string &s) {
        int pos = 0;
        for (auto f : s) {
            int c = f - 'a';
            if (nodes[pos].child[c] == -1) return {-1, -1};
            pos = nodes[pos].child[c];
        }
        return {nodes[pos].in, nodes[pos].out}; // Kiểm tra có xâu nào
                                        // kết thúc tại đỉnh này hay không
    }
    void dfs(int u)
    {
        nodes[u].in = ++timedfs;
        for (int i = 0; i <= 4; i++)
        {
            if (nodes[u].child[i] == -1) continue;
            //ok = true;
            dfs(nodes[u].child[i]);
        }
        nodes[u].out = timedfs;
    }
} pre, suf;
vector<pair<int, int>> point[N + 5];
void make_point(int u)
{
    bool ok = false;
    for (int i = 0; i <= 4; i++)
    {
        if (suf.nodes[u].child[i] == -1) continue;
        ok = true;
        make_point(suf.nodes[u].child[i]);
    }
    int id = suf.nodes[u].id;
    id = make[id];
    if (suf.nodes[u].exist) point[pre.nodes[id].in].push_back({suf.nodes[u].in, pre.nodes[id].exist});
}
int ans[ar];
struct BIT
{
    int bit[N + 5];
    void update(int u, int v)
    {
        while(u <= N)
        {
            bit[u] += v;
            u += u & (-u);
        }
    }
    int get(int u)
    {
        int ans = 0;
        while(u > 0)
        {
            ans += bit[u];
            u -= u & (-u);
        }
        return ans;
    }
} tree;
vector<tuple<int, int, int>> sta[N + 5], en[N + 5];
void get()
{
    for (int x = 1; x <= N; x++)
    {
        for (auto [y, v] : point[x]) tree.update(y, v);
        for (auto [l, r, i] : sta[x])
        {
            ans[i] -= tree.get(r) - tree.get(l - 1);
        }
        for (auto [l, r, i] : en[x])
        {
            ans[i] += tree.get(r) - tree.get(l - 1);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        r[i] = s[i];
        reverse(r[i].begin(), r[i].end());
        remake(s[i]);
        remake(r[i]);
        //cout << s[i] << ' ' << r[i] << '\n';
        pre.add_string(s[i], i, 1);
        suf.add_string(r[i], i, 0);
    }
    pre.dfs(0);
    suf.dfs(0);
    make_point(0);
    for (int i = 1; i <= m; i++)
    {
        cin >> p[i] >> q[i];
        remake(p[i]);
        remake(q[i]);
        reverse(q[i].begin(), q[i].end());
        auto [l1, r1] = pre.find(p[i]);
        auto [l2, r2] = suf.find(q[i]);
        if (l1 == -1) continue;
        //cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
        sta[l1 - 1].push_back({l2, r2, i});
        en[r1].push_back({l2, r2, i});
    }
    get();
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Compilation message

selling_rna.cpp: In function 'void make_point(int)':
selling_rna.cpp:87:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   87 |     bool ok = false;
      |          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164184 KB Output is correct
2 Correct 28 ms 164188 KB Output is correct
3 Correct 26 ms 162140 KB Output is correct
4 Correct 26 ms 164116 KB Output is correct
5 Correct 26 ms 164188 KB Output is correct
6 Correct 27 ms 164184 KB Output is correct
7 Correct 27 ms 162140 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 183632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 164040 KB Output is correct
2 Correct 34 ms 165456 KB Output is correct
3 Correct 35 ms 163932 KB Output is correct
4 Correct 32 ms 165460 KB Output is correct
5 Correct 32 ms 163272 KB Output is correct
6 Correct 36 ms 165712 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 164184 KB Output is correct
2 Correct 28 ms 164188 KB Output is correct
3 Correct 26 ms 162140 KB Output is correct
4 Correct 26 ms 164116 KB Output is correct
5 Correct 26 ms 164188 KB Output is correct
6 Correct 27 ms 164184 KB Output is correct
7 Correct 27 ms 162140 KB Output is correct
8 Incorrect 63 ms 183632 KB Output isn't correct
9 Halted 0 ms 0 KB -