Submission #146394

#	Time	Username	Problem	Language	Result	Execution time	Memory
146394		osaaateiasavtnl	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	953 ms	580444 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40