oj.uz

Submission #396534

# Submission time Handle Problem Language Result Execution time Memory
396534 2021-04-30T07:18:16 Z Sundavar Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 561 ms 344368 KB 
#include <bits/stdc++.h>

using namespace std;
int get(char c){
    if(c == 'A') return 1;
    if(c == 'G') return 2;
    if(c == 'C') return 3;
    return 0;
}
struct node{
    vector<int> to;
    vector<int> veg, pont;
    int cnt = 0;
    node(){
        to.resize(4, -1);
    }
};
vector<node> trie(1), rev(1);
int add(vector<node>& t, string s, int id, bool normal = true){
    int poz = 0;
    for(char& c: s){
        int k = get(c);
        if(t[poz].to[k] == -1){
            t[poz].to[k] = t.size();
            t.push_back(node());
        }
        t[poz = t[poz].to[k]].cnt++;
    }
    if(normal) t[poz].veg.push_back(id);
    else t[poz].pont.push_back(id);
    return poz;
}
vector<int> poz;
vector<int> ans;
vector<string> p,q, revs;
void walk(int curr){
    for(int& a : trie[curr].pont)
        ans[a] -= rev[poz[a]].cnt;
    for(int& a : trie[curr].veg)
        add(rev, revs[a], a);
    for(int& to : trie[curr].to){
        if(to == -1) continue;
        walk(to);
    }
    for(int& a : trie[curr].pont)
        ans[a] += rev[poz[a]].cnt;
}

int main(){
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<string> s(n);
    for(int i = 0; i < n; i++){
        cin>>s[i];
        add(trie, s[i], i);
        revs.push_back(s[i]), reverse(revs[i].begin(), revs[i].end());
    }
    poz.resize(m), ans.resize(m);
    p.resize(m), q.resize(m);
    for(int i = 0; i < m; i++){
        cin>>p[i]>>q[i];
        reverse(q[i].begin(), q[i].end());
        add(trie, p[i], i, false);
        poz[i] = add(rev, q[i], i, false);
    }
    walk(0);
    for(int& a : ans)
        cout<<a<<"\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 223444 KB Output is correct
2 Correct 422 ms 212012 KB Output is correct
3 Correct 426 ms 220680 KB Output is correct
4 Correct 414 ms 210512 KB Output is correct
5 Correct 557 ms 342260 KB Output is correct
6 Correct 561 ms 344368 KB Output is correct
7 Correct 74 ms 8816 KB Output is correct
8 Correct 359 ms 206856 KB Output is correct
9 Correct 326 ms 193220 KB Output is correct
10 Correct 281 ms 194316 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8208 KB Output is correct
2 Correct 23 ms 6084 KB Output is correct
3 Correct 30 ms 7084 KB Output is correct
4 Correct 26 ms 5612 KB Output is correct
5 Correct 25 ms 5684 KB Output is correct
6 Correct 29 ms 6928 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 366 ms 223444 KB Output is correct
9 Correct 422 ms 212012 KB Output is correct
10 Correct 426 ms 220680 KB Output is correct
11 Correct 414 ms 210512 KB Output is correct
12 Correct 557 ms 342260 KB Output is correct
13 Correct 561 ms 344368 KB Output is correct
14 Correct 74 ms 8816 KB Output is correct
15 Correct 359 ms 206856 KB Output is correct
16 Correct 326 ms 193220 KB Output is correct
17 Correct 281 ms 194316 KB Output is correct
18 Correct 30 ms 8208 KB Output is correct
19 Correct 23 ms 6084 KB Output is correct
20 Correct 30 ms 7084 KB Output is correct
21 Correct 26 ms 5612 KB Output is correct
22 Correct 25 ms 5684 KB Output is correct
23 Correct 29 ms 6928 KB Output is correct
24 Correct 356 ms 207472 KB Output is correct
25 Correct 376 ms 210224 KB Output is correct
26 Correct 348 ms 206488 KB Output is correct
27 Correct 408 ms 200140 KB Output is correct
28 Correct 189 ms 48568 KB Output is correct
29 Correct 100 ms 15956 KB Output is correct