oj.uz

Submission #339415

# Submission time Handle Problem Language Result Execution time Memory
339415 2020-12-25T07:49:09 Z ijxjdjd Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 640 ms 276940 KB 
#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)(4e6) + 5;
//const int MAXN = 5;
//const int MAXNODES = 20;
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;
    bool st = false;
    Trie() {
        root = nodes.size();
        nodes.push_back({});
    }
    int add(int i, vi& a) {
        sz += a.size();
        leaves.push_back(i);
        return iter(root, 0, i, a);
    }
    int iter(int j, int cur, int i, vi& s) {
        nodes[j].cnt++;
        if (cur == s.size()) {
            int old = nodes[j].leaf;
            if (old == -1) {
                nodes[j].leaf = i;
            }
            return old;
        }
        if (nodes[j].to[s[cur]] == -1) {
            nodes[j].to[s[cur]] = nodes.size();
            nodes.push_back({});
        }
        return 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() {
//    str s = "input.in";
//    freopen(s.c_str(), "r", stdin);
    start.st = true;
    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());
        int o = start.add(i, ss[i]);
        if (o == -1) {
            ts[i].add(i, ssrev[i]);
        }
        else {
            ts[o].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

selling_rna.cpp: In member function 'int Trie::iter(int, int, int, vi&)':
selling_rna.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (cur == s.size()) {
      |             ~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::cnt(vi&, int, int)':
selling_rna.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         if (cur == a.size()) {
      |             ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(int, vi&)':
selling_rna.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         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:137:9: note: in expansion of macro 'FR'
  137 |         FR(j, t.size()) {
      |         ^~
selling_rna.cpp:138:38: warning: array subscript has type 'char' [-Wchar-subscripts]
  138 |             ss[i].push_back(conv[t[j]]);
      |                                      ^
selling_rna.cpp:139:41: warning: array subscript has type 'char' [-Wchar-subscripts]
  139 |             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:154:9: note: in expansion of macro 'FR'
  154 |         FR(j, pre.size()) {
      |         ^~
selling_rna.cpp:155:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  155 |             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:157:9: note: in expansion of macro 'FR'
  157 |         FR(j, suff.size()) {
      |         ^~
selling_rna.cpp:158:45: warning: array subscript has type 'char' [-Wchar-subscripts]
  158 |             suffix[i].push_back(conv[suff[j]]);
      |                                             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32224 KB Output is correct
2 Correct 23 ms 32224 KB Output is correct
3 Correct 22 ms 32224 KB Output is correct
4 Correct 23 ms 32224 KB Output is correct
5 Correct 23 ms 32224 KB Output is correct
6 Correct 23 ms 32224 KB Output is correct
7 Correct 22 ms 32224 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 271448 KB Output is correct
2 Correct 523 ms 275472 KB Output is correct
3 Correct 517 ms 164752 KB Output is correct
4 Correct 523 ms 160912 KB Output is correct
5 Correct 579 ms 250128 KB Output is correct
6 Correct 586 ms 250264 KB Output is correct
7 Correct 436 ms 123380 KB Output is correct
8 Correct 640 ms 276852 KB Output is correct
9 Correct 564 ms 171152 KB Output is correct
10 Correct 521 ms 262928 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 40288 KB Output is correct
2 Correct 82 ms 38624 KB Output is correct
3 Correct 82 ms 39776 KB Output is correct
4 Correct 77 ms 37728 KB Output is correct
5 Correct 79 ms 38240 KB Output is correct
6 Correct 86 ms 39520 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32224 KB Output is correct
2 Correct 23 ms 32224 KB Output is correct
3 Correct 22 ms 32224 KB Output is correct
4 Correct 23 ms 32224 KB Output is correct
5 Correct 23 ms 32224 KB Output is correct
6 Correct 23 ms 32224 KB Output is correct
7 Correct 22 ms 32224 KB Output is correct
8 Correct 509 ms 271448 KB Output is correct
9 Correct 523 ms 275472 KB Output is correct
10 Correct 517 ms 164752 KB Output is correct
11 Correct 523 ms 160912 KB Output is correct
12 Correct 579 ms 250128 KB Output is correct
13 Correct 586 ms 250264 KB Output is correct
14 Correct 436 ms 123380 KB Output is correct
15 Correct 640 ms 276852 KB Output is correct
16 Correct 564 ms 171152 KB Output is correct
17 Correct 521 ms 262928 KB Output is correct
18 Correct 83 ms 40288 KB Output is correct
19 Correct 82 ms 38624 KB Output is correct
20 Correct 82 ms 39776 KB Output is correct
21 Correct 77 ms 37728 KB Output is correct
22 Correct 79 ms 38240 KB Output is correct
23 Correct 86 ms 39520 KB Output is correct
24 Correct 558 ms 275308 KB Output is correct
25 Correct 640 ms 276940 KB Output is correct
26 Correct 539 ms 275324 KB Output is correct
27 Correct 541 ms 151980 KB Output is correct
28 Correct 639 ms 111328 KB Output is correct
29 Correct 397 ms 71648 KB Output is correct