Submission #380554

#	Time	Username	Problem	Language	Result	Execution time	Memory
380554		pure_mem	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	942 ms	523584 KiB

selling_rna

#include <bits/stdc++.h>
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 1e5 + 12, MX = 2e6 + 12;
const ll INF = 1e18;

unordered_map<char, int> bor1[MX], bor2[MX];
vector< int > mark[MX], term[MX];
int ptr1 = 1, ptr2 = 1, n, m;
int tin[MX], tout[MX], timer;
string t[N];

void dfs(int v){
	tin[v] = ++timer;
	for(int id: mark[v]){
		int u = 1;
		for(int j = 0;j < (int)t[id].size();j++){
			if(!bor1[u].count(t[id][j]))
				bor1[u][t[id][j]] = ++ptr1;
			u = bor1[u][t[id][j]];	
			term[u].push_back(v);
		}
	}
	for(pair<char, int> to: bor2[v]){
		dfs(to.Y);	
	}
	tout[v] = timer;
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> t[i];
		int v = 1;
		for(int j = (int)t[i].size() - 1;j >= 0;j--){
			if(!bor2[v].count(t[i][j]))
				bor2[v][t[i][j]] = ++ptr2;
			v = bor2[v][t[i][j]];	
		} mark[v].push_back(i);
	}
	dfs(1);
	for(int i = 1;i <= m;i++){
		string s1, s2;
		cin >> s1 >> s2;
		int v = 1, good = 1;
		for(int j = (int)s2.size() - 1;j >= 0;j--){
			if(!bor2[v].count(s2[j])){
				good = 0;
				break;
			}
			v = bor2[v][s2[j]];
		}
		int u = 1;
		for(int j = 0;j < (int)s1.size();j++){
			if(!bor1[u].count(s1[j])){
				good = 0;
				break;
			}
			u = bor1[u][s1[j]];
		}
		int ans = 0;
		if(good){
			int tl = 1, tr = term[u].size(), tp1 = term[u].size() + 1;	
			while(tl <= tr){
				int tm = (tl + tr) / 2;
				if(tin[v] <= tin[term[u][tm - 1]]){
					tr = tm - 1, tp1 = tm;
				}
				else{
					tl = tm + 1;
				}
			}
			tl = 1, tr = term[u].size(); int tp2 = term[u].size();
			while(tl <= tr){
				int tm = (tl + tr) / 2;
				if(tout[v] < tin[term[u][tm - 1]]){
					tr = tm - 1;
				}
				else{
					tl = tm + 1, tp2 = tm;
				}
			}
			ans = tp2 - tp1 + 1;
		}
		cout << ans << "\n";
	}
}

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