oj.uz

Submission #865438

# Submission time Handle Problem Language Result Execution time Memory
865438 2023-10-24T08:26:19 Z phongcd Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 142752 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 3e5 + 2;
const int M = 19;
const ll MOD = 1e9 + 7;
const ll INF = 2e9;
const ll base = 311;
const ll base2 = 1e4 + 7;
const int BLOCK_SIZE = 400;

int n, m, cur = -1;
int cid[200];
string p, s;

struct node {
    int cnt, child[4][4];
}; vector <node> a;

int new_node() {
    node tmp;
    memset(tmp.child, -1, sizeof tmp.child);
    tmp.cnt = 0;
    a.push_back(tmp);
    return ++cur;
}

void add_node(string s) {
    int pos = 0, n = s.size();
    for (int i = 0; i < n; i ++) {
        int u = cid[s[i]];
        int v = cid[s[n - i - 1]];
        if (a[pos].child[u][v] < 0) {
            int tmp = new_node();
            a[pos].child[u][v] = tmp;
        }
        pos = a[pos].child[u][v];
        a[pos].cnt ++;
    }
}

int dfs(int u, int d) {
    if (d == max(p.size(), s.size())) 
        return a[u].cnt;
    
    int x = (d < p.size() ? cid[p[d]] : -1);
    int y = (d < s.size() ? cid[s[d]] : -1);

    ll res = 0;
    if (x != -1 && y != -1) {
        if (a[u].child[x][y] != -1)
            res = dfs(a[u].child[x][y], d + 1);
    }
    else if (x == -1) {
        for (int i = 0; i < 4; i ++)
            if (a[u].child[i][y] != -1)
                res += dfs(a[u].child[i][y], d + 1);
    }
    else {
        for (int i = 0; i < 4; i ++)
            if (a[u].child[x][i] != -1)
                res += dfs(a[u].child[x][i], d + 1);
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cid['A'] = 0, cid['G'] = 1, cid['C'] = 2, cid['U'] = 3;
    new_node();

    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        cin >> s;
        add_node(s);
    }

    while (m --) {
        cin >> p >> s;
        reverse(all(s));
        cout << dfs(0, 0) << '\n';
    }
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Compilation message

selling_rna.cpp: In function 'void add_node(std::string)':
selling_rna.cpp:40:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |         int u = cid[s[i]];
      |                         ^
selling_rna.cpp:41:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   41 |         int v = cid[s[n - i - 1]];
      |                                 ^
selling_rna.cpp: In function 'int dfs(int, int)':
selling_rna.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   52 |     if (d == max(p.size(), s.size()))
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     int x = (d < p.size() ? cid[p[d]] : -1);
      |              ~~^~~~~~~~~~
selling_rna.cpp:55:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |     int x = (d < p.size() ? cid[p[d]] : -1);
      |                                     ^
selling_rna.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     int y = (d < s.size() ? cid[s[d]] : -1);
      |              ~~^~~~~~~~~~
selling_rna.cpp:56:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |     int y = (d < s.size() ? cid[s[d]] : -1);
      |                                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1551 ms 142752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1116 KB Output is correct
2 Correct 17 ms 1224 KB Output is correct
3 Correct 14 ms 1224 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 17 ms 1228 KB Output is correct
6 Correct 13 ms 1092 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1551 ms 142752 KB Time limit exceeded
9 Halted 0 ms 0 KB -