oj.uz

Submission #380553

# Submission time Handle Problem Language Result Execution time Memory
380553 2021-03-22T09:19:05 Z pure_mem Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 588 ms 564332 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[N], 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 204 ms 272108 KB Output is correct
2 Correct 203 ms 271980 KB Output is correct
3 Correct 205 ms 271980 KB Output is correct
4 Correct 207 ms 271980 KB Output is correct
5 Correct 204 ms 271980 KB Output is correct
6 Correct 212 ms 272108 KB Output is correct
7 Correct 212 ms 272064 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 588 ms 564332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 273600 KB Output is correct
2 Correct 239 ms 273516 KB Output is correct
3 Correct 244 ms 273520 KB Output is correct
4 Correct 230 ms 273388 KB Output is correct
5 Correct 237 ms 273516 KB Output is correct
6 Correct 236 ms 273516 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 272108 KB Output is correct
2 Correct 203 ms 271980 KB Output is correct
3 Correct 205 ms 271980 KB Output is correct
4 Correct 207 ms 271980 KB Output is correct
5 Correct 204 ms 271980 KB Output is correct
6 Correct 212 ms 272108 KB Output is correct
7 Correct 212 ms 272064 KB Output is correct
8 Runtime error 588 ms 564332 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -