oj.uz

Submission #396532

# Submission time Handle Problem Language Result Execution time Memory
396532 2021-04-30T07:14:48 Z Sundavar Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 676 ms 347348 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){
        if(t[poz].to[get(c)] == -1){
            t[poz].to[get(c)] = t.size();
            t.push_back(node());
        }
        t[poz = t[poz].to[get(c)]].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(){
    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 296 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 300 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 229140 KB Output is correct
2 Correct 464 ms 217652 KB Output is correct
3 Correct 596 ms 226300 KB Output is correct
4 Correct 524 ms 215932 KB Output is correct
5 Correct 676 ms 345248 KB Output is correct
6 Correct 635 ms 347348 KB Output is correct
7 Correct 191 ms 16324 KB Output is correct
8 Correct 490 ms 213028 KB Output is correct
9 Correct 451 ms 199396 KB Output is correct
10 Correct 359 ms 198676 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8632 KB Output is correct
2 Correct 36 ms 6376 KB Output is correct
3 Correct 44 ms 7340 KB Output is correct
4 Correct 36 ms 5836 KB Output is correct
5 Correct 35 ms 5912 KB Output is correct
6 Correct 45 ms 7284 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 296 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 475 ms 229140 KB Output is correct
9 Correct 464 ms 217652 KB Output is correct
10 Correct 596 ms 226300 KB Output is correct
11 Correct 524 ms 215932 KB Output is correct
12 Correct 676 ms 345248 KB Output is correct
13 Correct 635 ms 347348 KB Output is correct
14 Correct 191 ms 16324 KB Output is correct
15 Correct 490 ms 213028 KB Output is correct
16 Correct 451 ms 199396 KB Output is correct
17 Correct 359 ms 198676 KB Output is correct
18 Correct 46 ms 8632 KB Output is correct
19 Correct 36 ms 6376 KB Output is correct
20 Correct 44 ms 7340 KB Output is correct
21 Correct 36 ms 5836 KB Output is correct
22 Correct 35 ms 5912 KB Output is correct
23 Correct 45 ms 7284 KB Output is correct
24 Correct 466 ms 213096 KB Output is correct
25 Correct 486 ms 215996 KB Output is correct
26 Correct 448 ms 211980 KB Output is correct
27 Correct 505 ms 202020 KB Output is correct
28 Correct 301 ms 54336 KB Output is correct
29 Correct 194 ms 19248 KB Output is correct