Submission #197724

#	Time	Username	Problem	Language	Result	Execution time	Memory
197724		TAISA_	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	408 ms	238200 KiB

selling_rna

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using vi=vector<ll>;
using P=pair<int,int>;
int idx[26];
struct Node{
	char c;
	int idx,out;
	Node* to[4];
	vector<int> vs;
	Node(char cc){
		c=cc;
		idx=-1;
		out=-1;
		for(int i=0;i<4;i++){
			to[i]=nullptr;
		}
	}
};
struct Trie{
	Node* rt;
	Trie(){
		rt=new Node('Z');
	}
	Node* insert(string& s,int t){
		Node* now=rt;
		for(int i=0;i<s.length();i++){
			Node* par=now;
			now=par->to[idx[s[i]-'A']];
			if(now==nullptr){
				now=new Node(s[i]);
				par->to[idx[s[i]-'A']]=now;
			}
			if(t!=-1){
				now->vs.emplace_back(t);
			}
		}
		return now;
	}
	int etour(Node* now,int id=-1){
		now->idx=id;
		for(int i=0;i<4;i++){
			if(now->to[i]!=nullptr){
				int to=etour(now->to[i],id+1);
				id=to;
			}
		}
		now->out=id;
		return id;
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	idx[0]=0;
	idx[2]=1;
	idx['G'-'A']=2;
	idx['U'-'A']=3;
	int n,m;cin>>n>>m;
	vector<string> s(n),p(m),q(m);
	Trie pre,suf;
	vector<Node*> en(m),nds(n);
	vector<P> vv;
	for(int i=0;i<n;i++){
		cin>>s[i];
		nds[i]=pre.insert(s[i],-1);
	}
	for(int i=0;i<m;i++){
		cin>>p[i]>>q[i];
		reverse(all(q[i]));
		en[i]=pre.insert(p[i],-1);
	}
	pre.etour(pre.rt);
	for(int i=0;i<n;i++){
		vv.emplace_back(P(nds[i]->idx,i));
	}
	sort(all(vv));
	for(int id=0;id<n;id++){
		int i=vv[id].second;
		reverse(all(s[i]));
		suf.insert(s[i],vv[id].first);
	}
	for(int i=0;i<m;i++){
		Node* nd=suf.insert(q[i],-1);
		int ub=en[i]->out,lb=en[i]->idx;
		int res=upper_bound(all(nd->vs),ub)-lower_bound(all(nd->vs),lb);
		cout<<res<<'\n';
	}
}

Compilation message (stderr)

selling_rna.cpp: In member function 'Node* Trie::insert(std::__cxx11::string&, int)':
selling_rna.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.length();i++){
               ~^~~~~~~~~~~

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