Submission #343126

#	Time	Username	Problem	Language	Result	Execution time	Memory
343126		sinamhdv	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	319 ms	153196 KiB

selling_rna

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define MAXL 2000100

int n, m;
vector<int> s[MAXN];
int sttime[MAXL], fntime[MAXL], timer;
int trie[MAXL][4];
int tn = 1;
int suftrie[MAXL][4];
int stn = 1;
int strend[MAXN];

vector<int> sts[MAXL];

inline void str2vec(const string &s, vector<int> &v)
{
	for (char c : s)
	{
		if (c == 'A')
			v.pb(0);
		else if (c == 'G')
			v.pb(1);
		else if (c == 'C')
			v.pb(2);
		else	// U
			v.pb(3);
	}
}

void add(const vector<int> &s, bool rev, int ind, int cld[MAXL][4])
{
	int &cnt = (rev ? stn : tn);
	int dir = (rev ? -1 : 1);
	int beg = 0;
	int end = s.size() - 1;
	if (rev)
		swap(beg, end);
	int v = 1;
	for (int i = beg; (rev && i >= end) || (!rev && i <= end); i += dir)
	{
		if (rev)
			sts[v].pb(sttime[strend[ind]]);
		int u = s[i];
		if (!cld[v][u])
		{
			cnt++;
			cld[v][u] = cnt;
		}
		v = cld[v][u];
	}
	if (rev)
		sts[v].pb(sttime[strend[ind]]);
	if (!rev)
		strend[ind] = v;
}

void dfs(int v)
{
	sttime[v] = timer++;
	FOR(i, 0, 4)
	{
		if (!trie[v][i])
			continue;
		dfs(trie[v][i]);
	}
	fntime[v] = timer;
}

int _find(const vector<int> &s, int trie[MAXL][4])
{
	int v = 1;
	for (int u : s)
	{
		if (!trie[v][u])
		{
			return -1;
		}
		v = trie[v][u];
	}
	return v;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 0, n)
	{
		string si;
		cin >> si;
		str2vec(si, s[i]);
		add(s[i], false, i, trie);
	}
	dfs(1);
	FOR(i, 0, n)
	{
		add(s[i], true, i, suftrie);
	}
	FOR(i, 1, stn + 1)
	{
		sort(all(sts[i]));
	}
	while (m--)
	{
		string p, q;
		cin >> p >> q;
		vector<int> pv, qv;
		str2vec(p, pv);
		str2vec(q, qv);
		reverse(all(qv));
		int lv = _find(pv, trie);
		int rv = _find(qv, suftrie);
		if (lv < 0 || rv < 0)
		{
			cout << 0 << endl;
			continue;
		}
		auto it1 = lower_bound(all(sts[rv]), sttime[lv]);
		auto it2 = lower_bound(all(sts[rv]), fntime[lv]);
		int ans = it2 - it1;
		cout << ans << endl;
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40