oj.uz

Submission #1083717

# Submission time Handle Problem Language Result Execution time Memory
1083717 2024-09-03T21:35:55 Z idiotcomputer Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 252 ms 229212 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define sz(x) (int) x.size()
#define pb push_back

const int mxN = 1e5+5;
const int mC = 2e6+5;
int n;

int v[mC];
vector<int> idxs[mC];
vector<int> adj[mC];
int cnt = 0;

int dfs(int node, int l, int r, int idx, string &s){
	if (idx == 0){
		return lower_bound(idxs[node].begin(), idxs[node].end(),r) - lower_bound(idxs[node].begin(),idxs[node].end(),l);
	}
	for (int i : adj[node]){
		if (v[i] == s[idx-1]-'A') return dfs(i,l,r,idx-1,s);
	}
	return 0;
}

void add(int node, int cidx, int idx, string &s){
	idxs[node].pb(cidx);
	if (idx == 0) return;
	for (int i : adj[node]){
		if (v[i] == s[idx-1]-'A') return add(i,cidx,idx-1,s);
	}
	v[cnt] = s[idx-1] - 'A';
	adj[node].pb(cnt);
	cnt++;
	return add(cnt-1,cidx,idx-1,s);
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int m;
	cin >> n >> m;

	vector<string> all(n);
	for (int i = 0; i < n; i++) cin >> all[i];
	sort(all.begin(),all.end());

	string temp;
	v[0] = 1;
	cnt++;
	for (int i = 0; i < n; i++){
		temp = all[i]+'B';
		add(0,i,sz(temp)-1,temp);
	} 
	

	int l,r;
	string a,b;
	for (int i = 0; i < m; i++){
		cin >> a >> b;
		l = lower_bound(all.begin(),all.end(), a) - all.begin();
		r = lower_bound(all.begin(),all.end(), a+'Z') - all.begin();
		temp = b + 'B';
		cout << dfs(0,l,r,sz(temp)-1,temp) << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94288 KB Output is correct
2 Correct 44 ms 94296 KB Output is correct
3 Correct 38 ms 94300 KB Output is correct
4 Correct 42 ms 94292 KB Output is correct
5 Correct 39 ms 94296 KB Output is correct
6 Correct 40 ms 94292 KB Output is correct
7 Correct 40 ms 94300 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 229212 KB Output is correct
2 Correct 227 ms 224576 KB Output is correct
3 Correct 111 ms 112208 KB Output is correct
4 Correct 108 ms 112220 KB Output is correct
5 Correct 163 ms 179768 KB Output is correct
6 Correct 158 ms 180564 KB Output is correct
7 Correct 89 ms 110420 KB Output is correct
8 Correct 183 ms 155476 KB Output is correct
9 Correct 161 ms 147792 KB Output is correct
10 Correct 130 ms 143892 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 96976 KB Output is correct
2 Correct 62 ms 96084 KB Output is correct
3 Correct 61 ms 96460 KB Output is correct
4 Correct 57 ms 96208 KB Output is correct
5 Correct 60 ms 96092 KB Output is correct
6 Correct 62 ms 96460 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94288 KB Output is correct
2 Correct 44 ms 94296 KB Output is correct
3 Correct 38 ms 94300 KB Output is correct
4 Correct 42 ms 94292 KB Output is correct
5 Correct 39 ms 94296 KB Output is correct
6 Correct 40 ms 94292 KB Output is correct
7 Correct 40 ms 94300 KB Output is correct
8 Correct 198 ms 229212 KB Output is correct
9 Correct 227 ms 224576 KB Output is correct
10 Correct 111 ms 112208 KB Output is correct
11 Correct 108 ms 112220 KB Output is correct
12 Correct 163 ms 179768 KB Output is correct
13 Correct 158 ms 180564 KB Output is correct
14 Correct 89 ms 110420 KB Output is correct
15 Correct 183 ms 155476 KB Output is correct
16 Correct 161 ms 147792 KB Output is correct
17 Correct 130 ms 143892 KB Output is correct
18 Correct 65 ms 96976 KB Output is correct
19 Correct 62 ms 96084 KB Output is correct
20 Correct 61 ms 96460 KB Output is correct
21 Correct 57 ms 96208 KB Output is correct
22 Correct 60 ms 96092 KB Output is correct
23 Correct 62 ms 96460 KB Output is correct
24 Correct 250 ms 207652 KB Output is correct
25 Correct 252 ms 207820 KB Output is correct
26 Correct 223 ms 206160 KB Output is correct
27 Correct 114 ms 111372 KB Output is correct
28 Correct 190 ms 127060 KB Output is correct
29 Correct 114 ms 106308 KB Output is correct