oj.uz

Submission #380554

# Submission time Handle Problem Language Result Execution time Memory
380554 2021-03-22T09:19:46 Z pure_mem Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 942 ms 523584 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 316652 KB Output is correct
2 Correct 233 ms 316652 KB Output is correct
3 Correct 236 ms 316652 KB Output is correct
4 Correct 260 ms 316652 KB Output is correct
5 Correct 234 ms 316652 KB Output is correct
6 Correct 235 ms 316652 KB Output is correct
7 Correct 266 ms 316780 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 473196 KB Output is correct
2 Correct 895 ms 464988 KB Output is correct
3 Correct 903 ms 505528 KB Output is correct
4 Correct 934 ms 496364 KB Output is correct
5 Correct 934 ms 520432 KB Output is correct
6 Correct 919 ms 523584 KB Output is correct
7 Correct 423 ms 332504 KB Output is correct
8 Correct 885 ms 447780 KB Output is correct
9 Correct 942 ms 428172 KB Output is correct
10 Correct 668 ms 423276 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 317672 KB Output is correct
2 Correct 269 ms 317804 KB Output is correct
3 Correct 275 ms 317932 KB Output is correct
4 Correct 263 ms 317548 KB Output is correct
5 Correct 267 ms 317804 KB Output is correct
6 Correct 269 ms 317804 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 316652 KB Output is correct
2 Correct 233 ms 316652 KB Output is correct
3 Correct 236 ms 316652 KB Output is correct
4 Correct 260 ms 316652 KB Output is correct
5 Correct 234 ms 316652 KB Output is correct
6 Correct 235 ms 316652 KB Output is correct
7 Correct 266 ms 316780 KB Output is correct
8 Correct 911 ms 473196 KB Output is correct
9 Correct 895 ms 464988 KB Output is correct
10 Correct 903 ms 505528 KB Output is correct
11 Correct 934 ms 496364 KB Output is correct
12 Correct 934 ms 520432 KB Output is correct
13 Correct 919 ms 523584 KB Output is correct
14 Correct 423 ms 332504 KB Output is correct
15 Correct 885 ms 447780 KB Output is correct
16 Correct 942 ms 428172 KB Output is correct
17 Correct 668 ms 423276 KB Output is correct
18 Correct 286 ms 317672 KB Output is correct
19 Correct 269 ms 317804 KB Output is correct
20 Correct 275 ms 317932 KB Output is correct
21 Correct 263 ms 317548 KB Output is correct
22 Correct 267 ms 317804 KB Output is correct
23 Correct 269 ms 317804 KB Output is correct
24 Correct 871 ms 446360 KB Output is correct
25 Correct 898 ms 446956 KB Output is correct
26 Correct 880 ms 445164 KB Output is correct
27 Correct 870 ms 472044 KB Output is correct
28 Correct 758 ms 348608 KB Output is correct
29 Correct 437 ms 325712 KB Output is correct