Submission #706485

#	Time	Username	Problem	Language	Result	Execution time	Memory
706485		AmirAli_H1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	555 ms	382540 KiB

selling_rna

// 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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40