Submission #896264

#	Time	Username	Problem	Language	Result	Execution time	Memory
896264		Minhbao	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1582 ms	595848 KiB

selling_rna

#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = double;
using str = string;
 
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
// #define mp make_pair
#define f first
#define s second
 
// vectors
// size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
// #define rtn return
 
#define lb lower_bound
#define ub upper_bound
 
/* Some Codes Skipped */
 
// loops
#define FOR(i,a,b) for (int (i) = (a); (i) < (b); ++(i))
#define REP(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int (i) = (b)-1; (i) >= (a); --(i))
#define PER(i,a) ROF(i,0,a)
#define rep(a) REP(_,a)
#define each(a,x) for (auto& a: x)
 
const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18;
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};   // for every grid problem
tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
    sort(all(v)); v.erase(unique(all(v)),end(v)); }
// Some Codes Skipped
 
inline namespace FileIO {
    void setIn(str s) {freopen(s.c_str(),"r", stdin);}
    void setOut(str s) {freopen(s.c_str(),"w", stdout);}
    void setIO() {
        cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
		 
        // cin.exceptions(cin.failbit);
        // throws exception when do smth illegal
        // ex. try to read letter into int
        // setIn("test.txt"), setOut("output.txt");    // for old USACO
    }
}



const int MAX_VALUE=4*4;

struct Node {
public:
    Node* child[MAX_VALUE];
    int exist, cnt, num;

    Node(){
        this->exist=0; this->cnt=0; this->num=0;
        for(int i=0;i<MAX_VALUE;++i) this->child[i]=NULL;
    }
};

map<char, int> index2;

struct Trie {
public:
    Node* root;
    Trie(){
        root=new Node();
    }
};

Trie* trie;

void addString(string s){
    Node* root=trie->root;
    for(int i=0;i<s.size();++i){
        root->cnt+=1;
        int ind=index2[s[i]];
        ind=ind*4+index2[s[s.size()-1-i]];
        if(root->child[ind]==NULL){
            root->child[ind]=new Node();
        }
        root=root->child[ind];
    }
    root->cnt+=1;
    root->exist+=1;
}

struct Item {
public:
    Node* node;
    int n;
    Item(Node* node, int n){
        this->node=node;
        this->n=n;
    }
};

int stringWithPreAndSuf(string p, string q){
    Node* root=trie->root;
    reverse(q.begin(), q.end());
    for(int i=0;i<min(p.size(), q.size());++i){
        int ind=index2[p[i]];
        ind=ind*4+index2[q[i]];
        Node* next=root->child[ind];
        if(next==NULL) return 0;
        root=next;
    }
    int cur=min(p.size(), q.size());
    if(p.size()==q.size()){
        return root->cnt;
    }
    bool prefix=true;
    if(p.size()<q.size()){
        swap(p, q);
        prefix=false;
    }
    queue<Item*> qu;
    qu.push(new Item(root, cur));
    int ans=0;
    while(qu.size()>0){
        Item* item=qu.front();
        qu.pop();
        if(item->n==p.size()) {
            ans+=item->node->cnt;
            continue;
        }
        for(int i=0;i<4;++i){
            int ind;
            if(prefix){
                ind=index2[p[item->n]]*4+i;
            }
            else{
                ind=i*4+index2[p[item->n]];
            }
            Node* next=item->node->child[ind];
            if(next!=NULL){
                qu.push(new Item(next, item->n+1));
            }
        }
    }
    return ans;
}

void solve(int tc){
    trie=new Trie();
    int n, m; cin>>n>>m;
    for(int i=0;i<n;++i){
        string s; cin>>s;
        addString(s);
    }
    for(int i=0;i<m;++i){
        string p, q; cin>>p>>q;
        cout<<stringWithPreAndSuf(p, q)<<"\n";
    }
}   
 
int main() {
    index2['A']=0;
    index2['C']=1;
    index2['G']=2;
    index2['U']=3;

    setIO();

    int tc=1;
	// cin>>tc;
	
	for(int i=1;i<=tc;++i){
		solve(i);
	}
}


 

Compilation message (stderr)

selling_rna.cpp: In function 'void addString(std::string)':
selling_rna.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i=0;i<s.size();++i){
      |                 ~^~~~~~~~~
selling_rna.cpp: In function 'int stringWithPreAndSuf(std::string, std::string)':
selling_rna.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
  142 |     for(int i=0;i<min(p.size(), q.size());++i){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:164:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         if(item->n==p.size()) {
      |            ~~~~~~~^~~~~~~~~~
selling_rna.cpp: In function 'void FileIO::setIn(str)':
selling_rna.cpp:75:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     void setIn(str s) {freopen(s.c_str(),"r", stdin);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void FileIO::setOut(str)':
selling_rna.cpp:76:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     void setOut(str s) {freopen(s.c_str(),"w", stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40