oj.uz

Submission #1083716

# Submission time Handle Problem Language Result Execution time Memory
1083716 2024-09-03T21:35:10 Z idiotcomputer Selling RNA Strands (JOI16_selling_rna) C++11
35 / 100
 188 ms 237840 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 = 1e6+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 20 ms 47192 KB Output is correct
2 Correct 20 ms 47324 KB Output is correct
3 Correct 18 ms 47464 KB Output is correct
4 Correct 21 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 22 ms 47196 KB Output is correct
7 Correct 18 ms 47196 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 188 ms 237840 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 44 ms 50128 KB Output is correct
2 Correct 39 ms 49240 KB Output is correct
3 Correct 47 ms 49472 KB Output is correct
4 Correct 36 ms 49236 KB Output is correct
5 Correct 36 ms 49488 KB Output is correct
6 Correct 43 ms 49324 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47192 KB Output is correct
2 Correct 20 ms 47324 KB Output is correct
3 Correct 18 ms 47464 KB Output is correct
4 Correct 21 ms 47196 KB Output is correct
5 Correct 21 ms 47196 KB Output is correct
6 Correct 22 ms 47196 KB Output is correct
7 Correct 18 ms 47196 KB Output is correct
8 Runtime error 188 ms 237840 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -