Submission #1279908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279908		sitingfake	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	609 ms	348740 KiB

selling_rna

//#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() {_
	// Do HLD on Trie
    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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40