oj.uz

Submission #706485

# Submission time Handle Problem Language Result Execution time Memory
706485 2023-03-06T17:41:18 Z AmirAli_H1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 555 ms 382540 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m;
const int maxn = 2e5 + 4;
const int maxs = 4e6 + 4;
string s[maxn];
pair<string, string> Q[maxn];
int t[maxs][4][2], sz[2] = {1, 1};
vector<int> Qa[maxs];
int M[maxs][2], cnt[maxs][2];
int big[maxs], S[maxs];
vector<string> gooni[maxs];
vector<char> vc;
int ans[maxn];

int GI(char ch) {
	if (ch == 'A') return 0;
	else if (ch == 'U') return 1;
	else if (ch == 'G') return 2;
	else return 3;
}

char GC(int val) {
	if (val == 0) return 'A';
	else if (val == 1) return 'U';
	else if (val == 2) return 'G';
	else return 'C';
}

void add(string s, int ind) {
	if (ind == 1) {
		string res = "";
		for (int i = 0; i < len(s); i++) res += s[len(s) - i - 1];
		s = res;
	}
	
	int v = 0;
	cnt[v][ind]++;
	for (int i = 0; i < len(s); i++) {
		int c = GI(s[i]);
		if (t[v][c][ind] == -1) v = t[v][c][ind] = sz[ind]++;
		else v = t[v][c][ind];
		cnt[v][ind]++;
	}
	M[v][ind]++;
}

void remove(string s, int ind) {
	if (ind == 1) {
		string res = "";
		for (int i = 0; i < len(s); i++) res += s[len(s) - i - 1];
		s = res;
	}
	
	int v = 0;
	cnt[v][ind]--;
	for (int i = 0; i < len(s); i++) {
		int c = GI(s[i]);
		if (t[v][c][ind] == -1) v = t[v][c][ind] = sz[ind]++;
		else v = t[v][c][ind];
		cnt[v][ind]--;
	}
	M[v][ind]--;
}

void addQ(string s, int i) {
	int v = 0, ind = 0;
	for (int i = 0; i < len(s); i++) {
		int c = GI(s[i]);
		if (t[v][c][ind] == -1) v = t[v][c][ind] = sz[ind]++;
		else v = t[v][c][ind];
	}
	Qa[v].pb(i);
}

int get_res(string s) {
	string res = "";
	for (int i = 0; i < len(s); i++) res += s[len(s) - i - 1];
	s = res;
	
	int v = 0, ind = 1;
	for (int i = 0; i < len(s); i++) {
		int c = GI(s[i]);
		if (t[v][c][ind] == -1) v = t[v][c][ind] = sz[ind]++;
		else v = t[v][c][ind];
	}
	return cnt[v][ind];
}

void pre_dfs(int v, int d = 0) {
	S[v] = M[v][0] * d; big[v] = -1;
	for (int i = 0; i < 4; i++) {
		int u = t[v][i][0];
		if (u != -1) {
			pre_dfs(u, d + 1);
			S[v] += S[u];
			if (big[v] == -1 || S[u] > S[big[v]]) big[v] = u;
		}
	}
}

void sack(int v, bool keep) {
	char w = '.';
	for (int i = 0; i < 4; i++) {
		int u = t[v][i][0];
		if (u != -1 && u != big[v]) {
			vc.pb(GC(i));
			sack(u, 0);
			vc.pop_back();
		}
		else if (u == big[v]) w = GC(i);
	}
	
	if (big[v] != -1) {
		vc.pb(w);
		sack(big[v], 1);
		vc.pop_back();
		swap(gooni[v], gooni[big[v]]);
	}
	
	string x = "";
	if (M[v][0] > 0) {
		for (char ch : vc) x += ch;
	}
	for (int T = 0; T < M[v][0]; T++) {
		gooni[v].pb(x);
		add(x, 1);
	}
	
	for (int i = 0; i < 4; i++) {
		int u = t[v][i][0];
		if (u != -1 && u != big[v]) {
			for (string s : gooni[u]) {
				gooni[v].pb(s);
				add(s, 1);
			}
			gooni[u].clear(); gooni[u].shrink_to_fit();
		}
	}
	
	for (int i : Qa[v]) {
		ans[i] = get_res(Q[i].S);
	}
	
	if (!keep) {
		for (string s : gooni[v]) {
			remove(s, 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	for (int i = 0; i < maxs; i++) {
		for (int T = 0; T < 4; T++) t[i][T][0] = t[i][T][1] = -1;
	}
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		add(s[i], 0);
	}
	
	for (int i = 0; i < m; i++) {
		string s1, s2;
		cin >> s1 >> s2;
		Q[i] = Mp(s1, s2);
		addQ(s1, i);
	}
	
	pre_dfs(0);
	sack(0, 1);
	
	for (int i = 0; i < m; i++) cout << ans[i] << endl;
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 332236 KB Output is correct
2 Correct 141 ms 332192 KB Output is correct
3 Correct 143 ms 332256 KB Output is correct
4 Correct 143 ms 332148 KB Output is correct
5 Correct 141 ms 332208 KB Output is correct
6 Correct 141 ms 332164 KB Output is correct
7 Correct 142 ms 332196 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 364956 KB Output is correct
2 Correct 269 ms 367812 KB Output is correct
3 Correct 547 ms 382088 KB Output is correct
4 Correct 555 ms 382540 KB Output is correct
5 Correct 482 ms 368236 KB Output is correct
6 Correct 478 ms 368796 KB Output is correct
7 Correct 204 ms 345420 KB Output is correct
8 Correct 359 ms 363992 KB Output is correct
9 Correct 310 ms 361164 KB Output is correct
10 Correct 381 ms 356172 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 336128 KB Output is correct
2 Correct 161 ms 334936 KB Output is correct
3 Correct 172 ms 336024 KB Output is correct
4 Correct 165 ms 336408 KB Output is correct
5 Correct 165 ms 334600 KB Output is correct
6 Correct 185 ms 335748 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 332236 KB Output is correct
2 Correct 141 ms 332192 KB Output is correct
3 Correct 143 ms 332256 KB Output is correct
4 Correct 143 ms 332148 KB Output is correct
5 Correct 141 ms 332208 KB Output is correct
6 Correct 141 ms 332164 KB Output is correct
7 Correct 142 ms 332196 KB Output is correct
8 Correct 264 ms 364956 KB Output is correct
9 Correct 269 ms 367812 KB Output is correct
10 Correct 547 ms 382088 KB Output is correct
11 Correct 555 ms 382540 KB Output is correct
12 Correct 482 ms 368236 KB Output is correct
13 Correct 478 ms 368796 KB Output is correct
14 Correct 204 ms 345420 KB Output is correct
15 Correct 359 ms 363992 KB Output is correct
16 Correct 310 ms 361164 KB Output is correct
17 Correct 381 ms 356172 KB Output is correct
18 Correct 165 ms 336128 KB Output is correct
19 Correct 161 ms 334936 KB Output is correct
20 Correct 172 ms 336024 KB Output is correct
21 Correct 165 ms 336408 KB Output is correct
22 Correct 165 ms 334600 KB Output is correct
23 Correct 185 ms 335748 KB Output is correct
24 Correct 288 ms 368088 KB Output is correct
25 Correct 308 ms 368716 KB Output is correct
26 Correct 304 ms 367820 KB Output is correct
27 Correct 552 ms 380272 KB Output is correct
28 Correct 350 ms 355400 KB Output is correct
29 Correct 270 ms 341784 KB Output is correct