oj.uz

Submission #250582

# Submission time Handle Problem Language Result Execution time Memory
250582 2020-07-18T12:46:43 Z parsa_mobed Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1248 ms 666044 KB 
#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(), v.end()
const int N = 2e6 + 1, M = 1e5 + 1;
int ans[M];
string s[M], p[M], q[M];
vector <int> Q[N], V[N];

void convert(string &s) {
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == 'A') s[i] = 0;
        if (s[i] == 'G') s[i] = 1;
        if (s[i] == 'C') s[i] = 2;
        if (s[i] == 'U') s[i] = 3;
    }
    return ;
}
struct Trie {
    int SGM;
    Trie(int sgm = 4) : SGM(sgm){}
    vector <int*> vec = {new int[SGM]{}};
    vector <int> cnt = {0}, subT = {0};
    inline void addv() {vec.push_back(new int[SGM]{}), cnt.push_back(0), subT.push_back(0); return ;}
    inline int* operator [] (int i) {return vec[i];}
    inline int add(const string &s) {
        int cur = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (!vec[cur][(int)s[i]]) vec[cur][(int)s[i]] = vec.size(), addv();
            subT[cur = vec[cur][(int)s[i]]]++;
        }
        cnt[cur]++;
        return cur;
    }
    inline int get(const string &s) {
        int cur = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (!vec[cur][(int)s[i]]) return 0;
            cur = vec[cur][(int)s[i]];
        }
        return cur;
    }
    inline int count(const string &s) {return subT[get(s)];}
    inline void clear() {
        vec.clear(), vec.shrink_to_fit();
        cnt.clear(), cnt.shrink_to_fit();
        subT.clear(), subT.shrink_to_fit();
        return ;
    }
    inline void swap(Trie &T) {
        vec.swap(T.vec);
        cnt.swap(T.cnt);
        subT.swap(T.subT);
        return ;
    }
} T, tri[N];

void dfs(int v) {
    int big = 0;
    for (int i = 0; i < 4; i++) if (T[v][i]) {
        dfs(T[v][i]);
        if (V[T[v][i]].size() > V[big].size()) big = T[v][i];
    }
    if (v == 0) return ;
    if (big == 0) for (int u : V[v]) tri[v].add(s[u]);
    else V[v].swap(V[big]), tri[v].swap(tri[big]);
    for (int i = 0; i < 4; i++) if (T[v][i]) {
        for (int u : V[T[v][i]]) V[v].push_back(u), tri[v].add(s[u]);
        V[T[v][i]].clear(), V[T[v][i]].shrink_to_fit();
        tri[T[v][i]].clear();
    }
    for (int i : Q[v]) ans[i] = tri[v].count(q[i]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i], convert(s[i]), V[T.add(s[i])].push_back(i), reverse(all(s[i]));
    for (int i = 0; i < m; i++) {
        cin >> p[i] >> q[i], convert(p[i]), convert(q[i]), reverse(all(q[i]));;
        int v = T.get(p[i]);
        if (v == 0) continue ;
        Q[v].push_back(i);
    }
    dfs(0);
    for (int i = 0; i < m; i++) cout << ans[i] << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 510712 KB Output is correct
2 Correct 564 ms 510928 KB Output is correct
3 Correct 482 ms 510840 KB Output is correct
4 Correct 538 ms 510716 KB Output is correct
5 Correct 561 ms 510724 KB Output is correct
6 Correct 537 ms 510712 KB Output is correct
7 Correct 576 ms 510712 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 663328 KB Output is correct
2 Correct 859 ms 660544 KB Output is correct
3 Correct 1155 ms 607716 KB Output is correct
4 Correct 1191 ms 602684 KB Output is correct
5 Correct 1184 ms 663612 KB Output is correct
6 Correct 1248 ms 666044 KB Output is correct
7 Correct 617 ms 517112 KB Output is correct
8 Correct 1030 ms 617936 KB Output is correct
9 Correct 901 ms 596816 KB Output is correct
10 Correct 1010 ms 618620 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 512120 KB Output is correct
2 Correct 554 ms 512120 KB Output is correct
3 Correct 545 ms 512120 KB Output is correct
4 Correct 644 ms 511480 KB Output is correct
5 Correct 582 ms 511780 KB Output is correct
6 Correct 574 ms 511864 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 510712 KB Output is correct
2 Correct 564 ms 510928 KB Output is correct
3 Correct 482 ms 510840 KB Output is correct
4 Correct 538 ms 510716 KB Output is correct
5 Correct 561 ms 510724 KB Output is correct
6 Correct 537 ms 510712 KB Output is correct
7 Correct 576 ms 510712 KB Output is correct
8 Correct 862 ms 663328 KB Output is correct
9 Correct 859 ms 660544 KB Output is correct
10 Correct 1155 ms 607716 KB Output is correct
11 Correct 1191 ms 602684 KB Output is correct
12 Correct 1184 ms 663612 KB Output is correct
13 Correct 1248 ms 666044 KB Output is correct
14 Correct 617 ms 517112 KB Output is correct
15 Correct 1030 ms 617936 KB Output is correct
16 Correct 901 ms 596816 KB Output is correct
17 Correct 1010 ms 618620 KB Output is correct
18 Correct 591 ms 512120 KB Output is correct
19 Correct 554 ms 512120 KB Output is correct
20 Correct 545 ms 512120 KB Output is correct
21 Correct 644 ms 511480 KB Output is correct
22 Correct 582 ms 511780 KB Output is correct
23 Correct 574 ms 511864 KB Output is correct
24 Correct 855 ms 649152 KB Output is correct
25 Correct 901 ms 650300 KB Output is correct
26 Correct 865 ms 647488 KB Output is correct
27 Correct 1093 ms 590528 KB Output is correct
28 Correct 782 ms 542956 KB Output is correct
29 Correct 692 ms 513080 KB Output is correct