제출 #954432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954432		amirhoseinfar1385	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	220 ms	303152 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,K=5,maxm=3000000+10;
int res[maxn],n,q;
string alls[maxn];
pair<string,string>allq[maxn];

struct triecnt{
	struct node{
		int allc[K],w;
		node(){
			w=0;
			allc[0]=allc[1]=allc[2]=allc[3]=allc[4]=-1;
		}
	};
	node tr[maxm];
	int te=1;
	void ins(string &s){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				tr[u].allc[v]=te;
				te++;
			}
			u=tr[u].allc[v];
			tr[u].w++;
		}
	}
	int pors(string &s){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				return 0;
			}
			u=tr[u].allc[v];
		}
		return tr[u].w;
	}
}trcnt;

struct trie{
	struct node{
		int allc[K];
		node(){
			allc[0]=allc[1]=allc[2]=allc[3]=allc[4]=-1;
		}
	};
	vector<int>qu[maxn],insy[maxn];
	node tr[maxm];
	int te=1;
	void ins(string &s,int ind){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				tr[u].allc[v]=te;
				te++;
			}
			u=tr[u].allc[v];
		}
		insy[u].push_back(ind);
	}
	void cal(string &s,int ind){
		int u=0;
		for(int i=0;i<(int)s.size();i++){
			int v=s[i]-'0';
			if(tr[u].allc[v]==-1){
				return ;
			}
			u=tr[u].allc[v];
		}
		qu[u].push_back(ind);
	}
	void calres(int u=0){
		if(u==-1){
			return ;
		}
		for(auto x:qu[u]){
			string fs=allq[x].second;
			reverse(fs.begin(),fs.end());
			res[x]=-trcnt.pors(fs);
			//cout<<"av: "<<u<<" "<<x<<" "<<res[x]<<endl;
		}
		for(auto x:insy[u]){
			string fs=alls[x];
			reverse(fs.begin(),fs.end());
			trcnt.ins(fs);
		}
		for(int i=0;i<5;i++){
			if(tr[u].allc[i]!=-1)
			//cout<<u<<" "<<tr[u].allc[i]<<endl;
			calres(tr[u].allc[i]);
		}
		for(auto x:qu[u]){
			string fs=allq[x].second;
			reverse(fs.begin(),fs.end());
			res[x]+=trcnt.pors(fs);
			//cout<<"dov: "<<u<<" "<<x<<" "<<res[x]<<endl;
		}
	}
}tri;

void tagh(string &s){
	for(int i=0;i<(int)s.size();i++){
		if(s[i]=='A'){
			s[i]='0';
		}else if(s[i]=='G'){
			s[i]='1';
		}else if(s[i]=='C'){
			s[i]='2';
		}else{
			s[i]='3';
		}
	}
}

void vorod(){
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>alls[i];
		tagh(alls[i]);
	}
	for(int i=0;i<q;i++){
		cin>>allq[i].first>>allq[i].second;
		tagh(allq[i].first);
		tagh(allq[i].second);
	}
}

void pre(){
	for(int i=0;i<n;i++){
		tri.ins(alls[i],i);
	}
	for(int i=0;i<q;i++){
		tri.cal(allq[i].first,i);
	}
	tri.calres();
}

void khor(){
	for(int i=0;i<q;i++){
		cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	khor();
}

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