oj.uz

Submission #748440

# Submission time Handle Problem Language Result Execution time Memory
748440 2023-05-26T09:39:08 Z guagua0407 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 515644 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;
int cur=0;

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){
    for(auto u:query[v]){
        ans[u]=query2(T2[u]);
    }
    for(auto u:vec){
        upd(rev[u],-1);
    }
    vector<int> num[4];
    for(auto u:vec){
        if(S[u].size()<=ord){
            continue;
        }
        num[mp[S[u][ord]]].push_back(u);
    }
    for(int i=0;i<4;i++){
        if(num[i].empty()) continue;
        for(auto u:num[i]){
            upd(rev[u],1);
        }
        dfs(trie[v][i],num[i],ord+1);
    }
}

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;
        upd(rev[i],1);
    }
    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:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<str.length();i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void insert1(std::string, int)':
selling_rna.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<str.length() and v!=-1;i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void upd(std::string, int)':
selling_rna.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<str.length();i++){
      |                 ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int query2(std::string)':
selling_rna.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     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: 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 220 ms 501216 KB Output is correct
2 Correct 220 ms 501260 KB Output is correct
3 Correct 224 ms 501332 KB Output is correct
4 Correct 228 ms 501204 KB Output is correct
5 Correct 227 ms 501208 KB Output is correct
6 Correct 223 ms 501352 KB Output is correct
7 Correct 229 ms 501324 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1603 ms 515644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 502760 KB Output is correct
2 Correct 274 ms 502568 KB Output is correct
3 Correct 257 ms 502624 KB Output is correct
4 Correct 248 ms 502208 KB Output is correct
5 Correct 261 ms 502224 KB Output is correct
6 Correct 267 ms 502420 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 501216 KB Output is correct
2 Correct 220 ms 501260 KB Output is correct
3 Correct 224 ms 501332 KB Output is correct
4 Correct 228 ms 501204 KB Output is correct
5 Correct 227 ms 501208 KB Output is correct
6 Correct 223 ms 501352 KB Output is correct
7 Correct 229 ms 501324 KB Output is correct
8 Execution timed out 1603 ms 515644 KB Time limit exceeded
9 Halted 0 ms 0 KB -