Submission #339381

#	Time	Username	Problem	Language	Result	Execution time	Memory
339381		ijxjdjd	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	478 ms	220048 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MAXN = (int)(1e5) + 5;
const int MAXNODES = (int)(2e6) + 5;
struct Node {
    int to[4] = {-1, -1, -1, -1};
    int leaf = -1;
    int cnt = 0;
};
vi prefix[MAXN];
vi suffix[MAXN];
int cur[MAXN];
int ans[MAXN];
vector<Node> nodes;
vi ss[MAXN];
vi ssrev[MAXN];
struct Trie {
    int root = -1;
    vector<int> leaves;
    int sz = 0;
    Trie() {
        root = nodes.size();
        nodes.push_back({});
    }
    void add(int i, vi& a) {
        sz += a.size();
        leaves.push_back(i);
        iter(root, 0, i, a);
    }
    void iter(int j, int cur, int i, vi& s) {
        nodes[j].cnt++;
        if (cur == s.size()-1) {
            nodes[j].leaf = i;
            return;
        }
        if (nodes[j].to[s[cur]] == -1) {
            nodes[j].to[s[cur]] = nodes.size();
            nodes.push_back({});
        }
        iter(nodes[j].to[s[cur]], cur+1, i, s);
    }
    int cnt(vi& a, int u, int cur = 0) {
        if (u == -1) {
            return 0;
        }
        if (cur == a.size()) {
            return nodes[u].cnt;
        }
        return cnt(a, nodes[u].to[a[cur]], cur+1);
    }
};
Trie start;
Trie ts[MAXN];
int tr[MAXNODES];
int merge(int u, int j) {
    if (ts[u].sz < ts[j].sz) {
        swap(u, j);
    }
    trav(v, ts[j].leaves) {
        ts[u].add(v, ssrev[v]);
    }
    return u;
}
void dfs(int u, vi& prefixes) {
    if (nodes[u].leaf != -1) {
        tr[u] = nodes[u].leaf;
    }
    vi send[5];
    trav(a, prefixes) {
        if (cur[a] == prefix[a].size()) {
            send[4].push_back(a);
        }
        else {
            send[prefix[a][cur[a]++]].push_back(a);
        }
    }
    FR(i, 4) {
        if (nodes[u].to[i] != -1) {
            dfs(nodes[u].to[i], send[i]);
            if (tr[u] == -1) {
                tr[u] = tr[nodes[u].to[i]];
            }
            else {
                tr[u] = merge(tr[u], tr[nodes[u].to[i]]);
            }
        }
    }
    trav(a, send[4]) {
        ans[a] = ts[tr[u]].cnt(suffix[a], ts[tr[u]].root);
    }

}
int conv[300];
int main() {
    int N, M;
    memset(ans, 0, sizeof(ans));
    cin >> N >> M;
    conv['A'] = 0;
    conv['G'] = 1;
    conv['C'] = 2;
    conv['U'] = 3;
    FR(i, MAXNODES) {
        tr[i] = -1;
    }
    FR(i, N) {
        string t;
        cin >> t;
        FR(j, t.size()) {
            ss[i].push_back(conv[t[j]]);
            ssrev[i].push_back(conv[t[j]]);
        }
        reverse(ssrev[i].begin(), ssrev[i].end());
        start.add(i, ss[i]);
        ts[i].add(i, ssrev[i]);
    }
    vi ori;
    FR(i, M) {
        string pre, suff;
        cin >> pre >> suff;
        FR(j, pre.size()) {
            prefix[i].push_back(conv[pre[j]]);
        }
        FR(j, suff.size()) {
            suffix[i].push_back(conv[suff[j]]);
        }
        reverse(suffix[i].begin(), suffix[i].end());
        ori.push_back(i);
    }
    dfs(start.root, ori);
    FR(i, M) {
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::iter(int, int, int, vi&)':
selling_rna.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (cur == s.size()-1) {
      |             ~~~~^~~~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::cnt(vi&, int, int)':
selling_rna.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if (cur == a.size()) {
      |             ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(int, vi&)':
selling_rna.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (cur[a] == prefix[a].size()) {
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
selling_rna.cpp:18:17: note: in expansion of macro 'FOR'
   18 | #define FR(i,a) FOR(i,0,a)
      |                 ^~~
selling_rna.cpp:127:9: note: in expansion of macro 'FR'
  127 |         FR(j, t.size()) {
      |         ^~
selling_rna.cpp:128:38: warning: array subscript has type 'char' [-Wchar-subscripts]
  128 |             ss[i].push_back(conv[t[j]]);
      |                                      ^
selling_rna.cpp:129:41: warning: array subscript has type 'char' [-Wchar-subscripts]
  129 |             ssrev[i].push_back(conv[t[j]]);
      |                                         ^
selling_rna.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
selling_rna.cpp:18:17: note: in expansion of macro 'FOR'
   18 | #define FR(i,a) FOR(i,0,a)
      |                 ^~~
selling_rna.cpp:139:9: note: in expansion of macro 'FR'
  139 |         FR(j, pre.size()) {
      |         ^~
selling_rna.cpp:140:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  140 |             prefix[i].push_back(conv[pre[j]]);
      |                                            ^
selling_rna.cpp:17:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
selling_rna.cpp:18:17: note: in expansion of macro 'FOR'
   18 | #define FR(i,a) FOR(i,0,a)
      |                 ^~~
selling_rna.cpp:142:9: note: in expansion of macro 'FR'
  142 |         FR(j, suff.size()) {
      |         ^~
selling_rna.cpp:143:45: warning: array subscript has type 'char' [-Wchar-subscripts]
  143 |             suffix[i].push_back(conv[suff[j]]);
      |                                             ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40