oj.uz

Submission #153936

# Submission time Handle Problem Language Result Execution time Memory
153936 2019-09-17T14:23:35 Z Mercenary Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 320 ms 145244 KB 
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

const int maxn = 1e5 + 5;
const int maxm = 2e6 + 6;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

int n , q;
int l[maxm][4] , r[maxm][4];
string s[maxn];

int converse(char x){
    if(x == 'A')return 0;
    if(x == 'G')return 1;
    if(x == 'C')return 2;
    return 3;
}

int in[maxm] , out[maxm];
vector<int> v[maxm];

int sz = 1 , sz1 = 1;
void add(int root , string &s , int id){
    for(const char & c : s){
        if(l[root][converse(c)] == 0)l[root][converse(c)] = ++sz;
        root = l[root][converse(c)];
    }
    if(in[root] == 0)in[root] = id;
    out[root] = id;
}
void addr(int root , string &s , int id){
    for(const char & c : s){
        if(r[root][converse(c)] == 0)r[root][converse(c)] = ++sz1;
        root = r[root][converse(c)];
        v[root].pb(id);
    }
}

int go(int root , string & s){
    for(const char & c : s){
        if(l[root][converse(c)] == 0)return 0;
        root = l[root][converse(c)];
    }
    return root;
}

int gor(int root , string & s){
    for(const char & c : s){
        if(r[root][converse(c)] == 0)return 0;
        root = r[root][converse(c)];
    }
    return root;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP", "r",stdin);
        freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> q;
    for(int i = 1 ; i <= n ; ++i){
        cin >> s[i];
    }
    sort(s + 1 , s + n + 1);
    for(int i = 1 ; i <= n ; ++i){
        add(1 , s[i] , i);
        reverse(s[i].begin(),s[i].end());
        addr(1 , s[i] , i);
    }
    function<void(int)> dfs = [&](int u){
        if(in[u] == 0)in[u] = 1e9;
        for(int i = 0 ; i < 4 ; ++i){
            if(l[u][i]){
                dfs(l[u][i]);
                in[u] = min(in[u] , in[l[u][i]]);
                out[u] = max(out[u] , out[l[u][i]]);
            }
        }
    };
    dfs(1);
    for(int i = 1 ; i <= sz1 ; ++i){
        sort(v[i].begin(),v[i].end());
    }
    while(q--){
        string p , q;cin >> p >> q;
        int x = go(1 , p);
        reverse(q.begin(),q.end());
        int y = gor(1 , q);
//        if(x == 0 || y == 0)continue;
        cout << upper_bound(v[y].begin(),v[y].end(),out[x]) -
        lower_bound(v[y].begin(),v[y].end(),in[x]) << '\n';
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 50424 KB Output is correct
2 Correct 50 ms 50424 KB Output is correct
3 Correct 49 ms 50428 KB Output is correct
4 Correct 60 ms 50424 KB Output is correct
5 Correct 60 ms 50552 KB Output is correct
6 Correct 60 ms 50424 KB Output is correct
7 Correct 49 ms 50424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 145244 KB Output is correct
2 Correct 310 ms 144304 KB Output is correct
3 Correct 280 ms 113540 KB Output is correct
4 Correct 283 ms 111004 KB Output is correct
5 Correct 306 ms 140156 KB Output is correct
6 Correct 311 ms 141484 KB Output is correct
7 Correct 138 ms 66016 KB Output is correct
8 Correct 285 ms 114680 KB Output is correct
9 Correct 248 ms 105976 KB Output is correct
10 Correct 230 ms 102624 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 51900 KB Output is correct
2 Correct 71 ms 51656 KB Output is correct
3 Correct 79 ms 51704 KB Output is correct
4 Correct 72 ms 51580 KB Output is correct
5 Correct 107 ms 51676 KB Output is correct
6 Correct 83 ms 51712 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 50424 KB Output is correct
2 Correct 50 ms 50424 KB Output is correct
3 Correct 49 ms 50428 KB Output is correct
4 Correct 60 ms 50424 KB Output is correct
5 Correct 60 ms 50552 KB Output is correct
6 Correct 60 ms 50424 KB Output is correct
7 Correct 49 ms 50424 KB Output is correct
8 Correct 318 ms 145244 KB Output is correct
9 Correct 310 ms 144304 KB Output is correct
10 Correct 280 ms 113540 KB Output is correct
11 Correct 283 ms 111004 KB Output is correct
12 Correct 306 ms 140156 KB Output is correct
13 Correct 311 ms 141484 KB Output is correct
14 Correct 138 ms 66016 KB Output is correct
15 Correct 285 ms 114680 KB Output is correct
16 Correct 248 ms 105976 KB Output is correct
17 Correct 230 ms 102624 KB Output is correct
18 Correct 80 ms 51900 KB Output is correct
19 Correct 71 ms 51656 KB Output is correct
20 Correct 79 ms 51704 KB Output is correct
21 Correct 72 ms 51580 KB Output is correct
22 Correct 107 ms 51676 KB Output is correct
23 Correct 83 ms 51712 KB Output is correct
24 Correct 306 ms 132444 KB Output is correct
25 Correct 320 ms 132640 KB Output is correct
26 Correct 316 ms 131480 KB Output is correct
27 Correct 244 ms 104440 KB Output is correct
28 Correct 280 ms 76152 KB Output is correct
29 Correct 152 ms 59128 KB Output is correct