oj.uz

Submission #153935

# Submission time Handle Problem Language Result Execution time Memory
153935 2019-09-17T14:21:20 Z Mercenary Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 383 ms 144060 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];
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){
        string s;cin >> s;
        add(1 , s , i);
        reverse(s.begin(),s.end());
        addr(1 , s , 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:62: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:63: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 383 ms 144060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 48696 KB Output is correct
2 Incorrect 75 ms 48768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -