oj.uz

Submission #748472

# Submission time Handle Problem Language Result Execution time Memory
748472 2023-05-26T10:38:02 Z guagua0407 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1144 ms 537720 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=2e6+5;
string S[mxn];
string rev[mxn];
string T1[mxn],T2[mxn];
int trie[mxn][4];
int trie2[mxn][4];
int cnt[mxn*4];
int ans[mxn];
vector<int> query[mxn*4];
map<char,int> mp;
map<int,char> mp2;
int cur=0;
string now="";

bool comp(vector<int> a,vector<int> b){
    return a.size()<b.size();
}

void insert(string str){
    int v=0;
    for(int i=0;i<str.length();i++){
        int a=mp[str[i]];
        if(trie[v][a]==-1){
            cur++;
            trie[v][a]=cur;
            v=cur;
        }
        else{
            v=trie[v][a];
        }
    }
}

void insert1(string str,int id){
    int v=0;
    for(int i=0;i<str.length() and v!=-1;i++){
        int a=mp[str[i]];
        v=trie[v][a];
    }
    if(v!=-1){
        query[v].push_back(id);
    }
}

void upd(string str,int d){
    int v=0;
    for(int i=0;i<str.length();i++){
        int a=mp[str[i]];
        if(trie2[v][a]==-1){
            cur++;
            trie2[v][a]=cur;
            v=cur;
        }
        else{
            v=trie2[v][a];
        }
        cnt[v]+=d;
    }
}

int query2(string str){
    int v=0;
    for(int i=0;i<str.length() and v!=-1;i++){
        int a=mp[str[i]];
        v=trie2[v][a];
    }
    if(v==-1) return 0;
    return cnt[v];
}

void dfs(int v,vector<int> vec,int ord=0){
    vector<int> num[4];
    for(auto u:vec){
        if(S[u].size()<=ord){
            continue;
        }
        num[mp[S[u][ord]]].push_back(u);
    }
    sort(num,num+4,comp);
    for(int i=0;i<4;i++){
        if(num[i].empty()) continue;
        int a=mp[S[num[i][0]][ord]];
        dfs(trie[v][a],num[i],ord+1);
        if(i==3) break;
        for(auto u:num[i]){
            upd(rev[u],-1);
        }
    }
    for(int i=0;i<3;i++){
        for(auto u:num[i]){
            upd(rev[u],1);
        }
    }
    for(auto u:vec){
        if(S[u].size()<=ord){
            upd(rev[u],1);
        }
    }
    for(auto u:query[v]){
        ans[u]=query2(T2[u]);
    }
}

int main() {_
    mp['A']=0;
    mp['G']=1;
    mp['C']=2;
    mp['U']=3;
    for(int i=0;i<mxn;i++){
        for(int j=0;j<4;j++){
            trie[i][j]=trie2[i][j]=-1;
        }
    }
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>S[i];
        rev[i]=S[i];
        reverse(all(rev[i]));
        insert(S[i]);
    }
    for(int i=0;i<m;i++){
        cin>>T1[i]>>T2[i];
        reverse(all(T2[i]));
        insert1(T1[i],i);
    }
    vector<int> vec(n);
    for(int i=0;i<n;i++){
        vec[i]=i;
    }
    dfs(0,vec);
    for(int i=0;i<m;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
//maybe its multiset not set

Compilation message

selling_rna.cpp: In function 'void insert(std::string)':
selling_rna.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<str.length();i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void insert1(std::string, int)':
selling_rna.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<str.length() and v!=-1;i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void upd(std::string, int)':
selling_rna.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<str.length();i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int query2(std::string)':
selling_rna.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<str.length() and v!=-1;i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void dfs(int, std::vector<int>, int)':
selling_rna.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(S[u].size()<=ord){
      |            ~~~~~~~~~~~^~~~~
selling_rna.cpp:110:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |         if(S[u].size()<=ord){
      |            ~~~~~~~~~~~^~~~~
selling_rna.cpp: In function 'void setIO(std::string)':
selling_rna.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 501208 KB Output is correct
2 Correct 240 ms 501428 KB Output is correct
3 Correct 228 ms 501300 KB Output is correct
4 Correct 220 ms 501240 KB Output is correct
5 Correct 217 ms 501276 KB Output is correct
6 Correct 214 ms 501264 KB Output is correct
7 Correct 245 ms 501188 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 537340 KB Output is correct
2 Correct 384 ms 537720 KB Output is correct
3 Correct 1144 ms 512712 KB Output is correct
4 Correct 1107 ms 512240 KB Output is correct
5 Correct 811 ms 515624 KB Output is correct
6 Correct 824 ms 515908 KB Output is correct
7 Correct 296 ms 528844 KB Output is correct
8 Correct 555 ms 524416 KB Output is correct
9 Correct 523 ms 525896 KB Output is correct
10 Correct 587 ms 521384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 503240 KB Output is correct
2 Correct 245 ms 503008 KB Output is correct
3 Correct 259 ms 502988 KB Output is correct
4 Correct 255 ms 502684 KB Output is correct
5 Correct 245 ms 502584 KB Output is correct
6 Correct 276 ms 502724 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 501208 KB Output is correct
2 Correct 240 ms 501428 KB Output is correct
3 Correct 228 ms 501300 KB Output is correct
4 Correct 220 ms 501240 KB Output is correct
5 Correct 217 ms 501276 KB Output is correct
6 Correct 214 ms 501264 KB Output is correct
7 Correct 245 ms 501188 KB Output is correct
8 Correct 384 ms 537340 KB Output is correct
9 Correct 384 ms 537720 KB Output is correct
10 Correct 1144 ms 512712 KB Output is correct
11 Correct 1107 ms 512240 KB Output is correct
12 Correct 811 ms 515624 KB Output is correct
13 Correct 824 ms 515908 KB Output is correct
14 Correct 296 ms 528844 KB Output is correct
15 Correct 555 ms 524416 KB Output is correct
16 Correct 523 ms 525896 KB Output is correct
17 Correct 587 ms 521384 KB Output is correct
18 Correct 242 ms 503240 KB Output is correct
19 Correct 245 ms 503008 KB Output is correct
20 Correct 259 ms 502988 KB Output is correct
21 Correct 255 ms 502684 KB Output is correct
22 Correct 245 ms 502584 KB Output is correct
23 Correct 276 ms 502724 KB Output is correct
24 Correct 398 ms 535980 KB Output is correct
25 Correct 400 ms 536924 KB Output is correct
26 Correct 395 ms 535692 KB Output is correct
27 Correct 1000 ms 512656 KB Output is correct
28 Correct 458 ms 531328 KB Output is correct
29 Correct 352 ms 509024 KB Output is correct