oj.uz

Submission #1100157

# Submission time Handle Problem Language Result Execution time Memory
1100157 2024-10-13T05:34:08 Z rayan_bd Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 95976 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long
const int mxN = 1e5;

unordered_map<char,ll> mp;
vector<ll> emp;

struct Node
{
	set<ll> end_pos;
	Node* children[4];
	bool end;
	Node(){
		end=0;
		for(ll i=0;i<4;++i) children[i]=NULL;
	}
};

struct Trie{
	Node* root = new Node();
	void add(string str){
		Node* curr = root;
		for(auto it:str){
			if(curr->children[mp[it]]==NULL) curr->children[mp[it]]=new Node();
			curr=curr->children[mp[it]];
		}
		curr->end=1;
	}
	void update_pos(string str,bool from_beg,ll idx){
		Node* curr=root;
		if(!from_beg){
			for(int i=str.size()-1;i>=0;--i){
				char it=str[i];
				if(curr->children[mp[it]]==NULL) return;
				curr=curr->children[mp[it]];
				if(curr->end){
					curr->end_pos.insert(idx);
				}
			}
			return;
		}
		for(auto it:str){
			if(curr->children[mp[it]]==NULL) return;
			curr=curr->children[mp[it]];
			if(curr->end){
				curr->end_pos.insert(idx);
			}
		}
	}
	set<ll> qry(string str){
		Node* curr = root;
		for(auto it:str){
			curr=curr->children[mp[it]];
		}
		return curr->end_pos;
	}
};

void solve(){
	mp['A']=0;
	mp['C']=1;
	mp['G']=2;
	mp['U']=3;

	Trie pre,suf;
	ll n,m;cin>>n>>m;
	vector<string> vec(n);
	vector<pair<string,string>> pr(m);
	for(ll i=0;i<n;++i){
		cin>>vec[i];
	}
	for(ll i=0;i<m;++i){
		cin>>pr[i].first>>pr[i].second;
		pre.add(pr[i].first);
		reverse(all(pr[i].second));
		suf.add(pr[i].second);
	}
	ll idx=0;
	for(auto it:vec){
		pre.update_pos(it,1,idx);
		suf.update_pos(it,0,idx);
		++idx;
	}
	for(auto it:pr){
		set<ll> c1=pre.qry(it.first);
		set<ll> c2=suf.qry(it.second);
		ll ans=0;
		if(c1.size()<=c2.size()){
			for(auto it:c1){
				ans+=c2.find(it)!=c2.end();
			}
		}else{
			for(auto it:c2){
				ans+=c1.find(it)!=c1.end();
			}
		}
		cout<<ans<<'\n';
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 356 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 60348 KB Output is correct
2 Execution timed out 1519 ms 95976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 459 ms 60348 KB Output is correct
9 Execution timed out 1519 ms 95976 KB Time limit exceeded
10 Halted 0 ms 0 KB -