Submission #155607

# Submission time Handle Problem Language Result Execution time Memory
155607 2019-09-29T08:29:50 Z georgerapeanu Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
336 ms 145528 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:32: 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:40: 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);
                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 47 ms 50552 KB Output is correct
2 Correct 47 ms 50552 KB Output is correct
3 Correct 47 ms 50424 KB Output is correct
4 Correct 47 ms 50424 KB Output is correct
5 Correct 48 ms 50424 KB Output is correct
6 Correct 47 ms 50424 KB Output is correct
7 Correct 47 ms 50424 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 316 ms 145528 KB Output is correct
2 Correct 299 ms 144184 KB Output is correct
3 Correct 268 ms 113472 KB Output is correct
4 Correct 254 ms 110964 KB Output is correct
5 Correct 298 ms 140156 KB Output is correct
6 Correct 336 ms 141364 KB Output is correct
7 Correct 132 ms 66040 KB Output is correct
8 Correct 284 ms 114664 KB Output is correct
9 Correct 254 ms 105948 KB Output is correct
10 Correct 217 ms 102648 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 77 ms 51288 KB Output is correct
2 Correct 73 ms 51272 KB Output is correct
3 Correct 78 ms 51752 KB Output is correct
4 Correct 69 ms 51576 KB Output is correct
5 Correct 74 ms 51704 KB Output is correct
6 Correct 79 ms 51704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 47 ms 50552 KB Output is correct
2 Correct 47 ms 50552 KB Output is correct
3 Correct 47 ms 50424 KB Output is correct
4 Correct 47 ms 50424 KB Output is correct
5 Correct 48 ms 50424 KB Output is correct
6 Correct 47 ms 50424 KB Output is correct
7 Correct 47 ms 50424 KB Output is correct
8 Correct 316 ms 145528 KB Output is correct
9 Correct 299 ms 144184 KB Output is correct
10 Correct 268 ms 113472 KB Output is correct
11 Correct 254 ms 110964 KB Output is correct
12 Correct 298 ms 140156 KB Output is correct
13 Correct 336 ms 141364 KB Output is correct
14 Correct 132 ms 66040 KB Output is correct
15 Correct 284 ms 114664 KB Output is correct
16 Correct 254 ms 105948 KB Output is correct
17 Correct 217 ms 102648 KB Output is correct
18 Correct 77 ms 51288 KB Output is correct
19 Correct 73 ms 51272 KB Output is correct
20 Correct 78 ms 51752 KB Output is correct
21 Correct 69 ms 51576 KB Output is correct
22 Correct 74 ms 51704 KB Output is correct
23 Correct 79 ms 51704 KB Output is correct
24 Correct 296 ms 132396 KB Output is correct
25 Correct 319 ms 132696 KB Output is correct
26 Correct 331 ms 131612 KB Output is correct
27 Correct 237 ms 104440 KB Output is correct
28 Correct 291 ms 76044 KB Output is correct
29 Correct 147 ms 58964 KB Output is correct