oj.uz

Submission #441665

# Submission time Handle Problem Language Result Execution time Memory
441665 2021-07-05T18:01:58 Z MladenP Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 237 ms 112212 KB 
#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define endl '\n'
using namespace std;
#define MAXL 2000010
#define MAXN 100010
int prefT[MAXL][4], suffT[MAXL][4], idx[MAXL], siz[MAXL], bit[MAXL], en[MAXL], cross[MAXL];
int rez[MAXN], prefIdx, suffIdx, nodeQ[MAXN];
vector<int> q[MAXL];
void update(int idx, int val) {
    while(idx < MAXL) {
        bit[idx] += val;
        idx += idx&-idx;
    }
}
int query(int idx) {
    int rez = 0;
    while(idx > 0) {
        rez += bit[idx];
        idx -= idx&-idx;
    }
    return rez;
}
int timer;
int eulerDFS(int node) {
    idx[node] = ++timer;
    siz[node] = 1;
    for(int i = 0; i < 4; i++) {
        if(suffT[node][i]) siz[node] += eulerDFS(suffT[node][i]);
    }
    return siz[node];
}
void solveDFS(int node) {
    for(auto x : q[node]) {
        int nd = nodeQ[x];
        rez[x] -= (query(idx[nd]+siz[nd]-1) - query(idx[nd]-1));
    }
    for(int i = 0; i < 4; i++) {
        if(prefT[node][i]) solveDFS(prefT[node][i]);
    }
    update(idx[cross[node]], +en[node]);
    for(auto x : q[node]) {
        int nd = nodeQ[x];
        rez[x] += (query(idx[nd]+siz[nd]-1) - query(idx[nd]-1));
    }
}
int ch(char c) {
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'C') return 2;
    if(c == 'U') return 3;
}
int add(int trie[][4], string &s, int &idxx, int save) {
    int node = 0, i = 0, n = s.size();
    while(i < n) {
        int c = ch(s[i]);
        if(!trie[node][c]) trie[node][c] = ++idxx;
        node = trie[node][c];
        i++;
    }
    if(save) en[node]++;
    return node;
}
int findT(int trie[][4], string &s) {
    int node = 0, i = 0, n = s.size();
    while(i < n) {
        int c = ch(s[i]);
        if(!trie[node][c]) return -1;
        node = trie[node][c];
        i++;
    }
    return node;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, M; cin >> N >> M;
    for(int i = 1; i <= N; i++) {
        string x; cin >> x;
        int nP = add(prefT, x, prefIdx, 1);
        reverse(all(x));
        int nS = add(suffT, x, suffIdx, 0);
        cross[nP] = nS;
    }
    eulerDFS(0);
    for(int i = 1; i <= M; i++) {
        string P, Q; cin >> P >> Q;
        reverse(all(Q));
        int nodeP = findT(prefT, P);
        nodeQ[i] = findT(suffT, Q);
        if(nodeP != -1 && nodeQ[i] != -1) {
            q[nodeP].push_back(i);
        }
    }
    solveDFS(0);
    for(int i = 1; i <= M; i++) {
        cout << rez[i] << endl;
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int ch(char)':
selling_rna.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47308 KB Output is correct
2 Correct 28 ms 47412 KB Output is correct
3 Correct 29 ms 47308 KB Output is correct
4 Correct 29 ms 47344 KB Output is correct
5 Correct 30 ms 47268 KB Output is correct
6 Correct 31 ms 47408 KB Output is correct
7 Correct 30 ms 47308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 101956 KB Output is correct
2 Correct 119 ms 100336 KB Output is correct
3 Correct 231 ms 91628 KB Output is correct
4 Correct 215 ms 91716 KB Output is correct
5 Correct 233 ms 111360 KB Output is correct
6 Correct 237 ms 112212 KB Output is correct
7 Correct 69 ms 49572 KB Output is correct
8 Correct 154 ms 85692 KB Output is correct
9 Correct 141 ms 79812 KB Output is correct
10 Correct 122 ms 78856 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 48832 KB Output is correct
2 Correct 45 ms 48392 KB Output is correct
3 Correct 49 ms 48652 KB Output is correct
4 Correct 45 ms 48324 KB Output is correct
5 Correct 45 ms 48416 KB Output is correct
6 Correct 50 ms 48452 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47308 KB Output is correct
2 Correct 28 ms 47412 KB Output is correct
3 Correct 29 ms 47308 KB Output is correct
4 Correct 29 ms 47344 KB Output is correct
5 Correct 30 ms 47268 KB Output is correct
6 Correct 31 ms 47408 KB Output is correct
7 Correct 30 ms 47308 KB Output is correct
8 Correct 125 ms 101956 KB Output is correct
9 Correct 119 ms 100336 KB Output is correct
10 Correct 231 ms 91628 KB Output is correct
11 Correct 215 ms 91716 KB Output is correct
12 Correct 233 ms 111360 KB Output is correct
13 Correct 237 ms 112212 KB Output is correct
14 Correct 69 ms 49572 KB Output is correct
15 Correct 154 ms 85692 KB Output is correct
16 Correct 141 ms 79812 KB Output is correct
17 Correct 122 ms 78856 KB Output is correct
18 Correct 49 ms 48832 KB Output is correct
19 Correct 45 ms 48392 KB Output is correct
20 Correct 49 ms 48652 KB Output is correct
21 Correct 45 ms 48324 KB Output is correct
22 Correct 45 ms 48416 KB Output is correct
23 Correct 50 ms 48452 KB Output is correct
24 Correct 118 ms 93616 KB Output is correct
25 Correct 128 ms 94232 KB Output is correct
26 Correct 112 ms 92992 KB Output is correct
27 Correct 206 ms 86864 KB Output is correct
28 Correct 118 ms 56884 KB Output is correct
29 Correct 89 ms 51140 KB Output is correct