oj.uz

Submission #146394

# Submission time Handle Problem Language Result Execution time Memory
146394 2019-08-23T18:23:49 Z osaaateiasavtnl Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 953 ms 580444 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
const int N = 1e5 + 7, C = 4;
vector <char> alp = {'A', 'G', 'C', 'U'};
int num(char c) { for (int i = 0; i < C; ++i) if (alp[i] == c) return i; }   
struct Node {
    int sum;
    Node *to[C];
    Node () {
        sum = 0;
        for (int i = 0; i < C; ++i) to[i] = NULL;
    }
};
struct Node1 {
    vector <int> a, q;
    Node1 *to[C];
    Node1 () {
        for (int i = 0; i < C; ++i) to[i] = NULL;
    }
};  
void add(Node *t, vector <int> &a) {
    ++t->sum;
    for (int c : a) {
        if (!t->to[c]) t->to[c] = new Node();
        t = t->to[c];
        ++t->sum;
    }
}
void add(Node1 *t, vector <int> &a, int i) {
    for (int c : a) {
        if (!t->to[c]) t->to[c] = new Node1();
        t = t->to[c];
    }   
    t->a.app(i);
}   
Node *merge(Node *l, Node *r) {
    if (!l) return r; if (!r) return l;
    Node *ans = new Node();
    ans->sum = l->sum + r->sum;
    for (int i = 0; i < C; ++i) ans->to[i] = merge(l->to[i], r->to[i]);
    return ans;
}
int n, m;
vector <int> a[N], l[N], r[N];
int ans[N];
Node* dfs(Node1 *t) {
    if (!t) return NULL;
    Node *res = new Node();
    for (int i : t->a) add(res, a[i]);
    for (int i = 0; i < C; ++i) res = merge(res, dfs(t->to[i]));
    for (int i : t->q) {
        Node *cur = res;
        for (char c : r[i]) {
            if (!cur->to[c]) { cur = NULL; break; }
            cur = cur->to[c];
        }
        if (cur) ans[i] = cur->sum;
    }
    return res;
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m;
    Node1 *root = new Node1();
    for (int i = 0; i < n; ++i) { 
        string s; cin >> s;
        for (char c : s) a[i].app(num(c));
        add(root, a[i], i); 
    }
    for (int i = 0; i < m; ++i) {
        string ls, rs; cin >> ls >> rs;
        for (char c : ls) l[i].app(num(c));
        for (char c : rs) r[i].app(num(c));
        reverse(all(r[i]));
        Node1 *cur = root;
        for (char c : l[i]) {
            if (!cur->to[c]) { cur = NULL; break; }
            cur = cur->to[c];
        }
        if (cur) cur->q.app(i);
    }
    for (int i = 0; i < n; ++i) reverse(all(a[i]));
    dfs(root);
    for (int i = 0; i < m; ++i) cout << ans[i] << '\n';    
}

Compilation message

selling_rna.cpp: In function 'Node* merge(Node*, Node*)':
selling_rna.cpp:42:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (!l) return r; if (!r) return l;
     ^~
selling_rna.cpp:42:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if (!l) return r; if (!r) return l;
                       ^~
selling_rna.cpp: In function 'Node* dfs(Node1*)':
selling_rna.cpp:59:27: warning: array subscript has type 'char' [-Wchar-subscripts]
             if (!cur->to[c]) { cur = NULL; break; }
                           ^
selling_rna.cpp:60:28: warning: array subscript has type 'char' [-Wchar-subscripts]
             cur = cur->to[c];
                            ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:86:27: warning: array subscript has type 'char' [-Wchar-subscripts]
             if (!cur->to[c]) { cur = NULL; break; }
                           ^
selling_rna.cpp:87:28: warning: array subscript has type 'char' [-Wchar-subscripts]
             cur = cur->to[c];
                            ^
selling_rna.cpp: In function 'int num(char)':
selling_rna.cpp:10:74: warning: control reaches end of non-void function [-Wreturn-type]
 int num(char c) { for (int i = 0; i < C; ++i) if (alp[i] == c) return i; }   
                                                                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7672 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 8 ms 7388 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 127784 KB Output is correct
2 Correct 245 ms 125092 KB Output is correct
3 Correct 953 ms 580444 KB Output is correct
4 Correct 918 ms 554544 KB Output is correct
5 Correct 555 ms 312184 KB Output is correct
6 Correct 561 ms 316608 KB Output is correct
7 Correct 348 ms 185080 KB Output is correct
8 Correct 593 ms 327160 KB Output is correct
9 Correct 541 ms 288248 KB Output is correct
10 Correct 387 ms 222840 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13424 KB Output is correct
2 Correct 41 ms 12156 KB Output is correct
3 Correct 46 ms 13048 KB Output is correct
4 Correct 42 ms 11512 KB Output is correct
5 Correct 43 ms 12920 KB Output is correct
6 Correct 48 ms 13304 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7672 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 8 ms 7388 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 251 ms 127784 KB Output is correct
9 Correct 245 ms 125092 KB Output is correct
10 Correct 953 ms 580444 KB Output is correct
11 Correct 918 ms 554544 KB Output is correct
12 Correct 555 ms 312184 KB Output is correct
13 Correct 561 ms 316608 KB Output is correct
14 Correct 348 ms 185080 KB Output is correct
15 Correct 593 ms 327160 KB Output is correct
16 Correct 541 ms 288248 KB Output is correct
17 Correct 387 ms 222840 KB Output is correct
18 Correct 49 ms 13424 KB Output is correct
19 Correct 41 ms 12156 KB Output is correct
20 Correct 46 ms 13048 KB Output is correct
21 Correct 42 ms 11512 KB Output is correct
22 Correct 43 ms 12920 KB Output is correct
23 Correct 48 ms 13304 KB Output is correct
24 Correct 239 ms 115548 KB Output is correct
25 Correct 265 ms 117532 KB Output is correct
26 Correct 233 ms 113824 KB Output is correct
27 Correct 839 ms 482808 KB Output is correct
28 Correct 266 ms 55772 KB Output is correct
29 Correct 205 ms 35996 KB Output is correct