oj.uz

Submission #528826

# Submission time Handle Problem Language Result Execution time Memory
528826 2022-02-21T14:12:14 Z AriaH Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 529 ms 436944 KB 
/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

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

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 2e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
const int sigma = 4;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

struct Trie
{
	int ptr, sub[N], nxt[sigma][N];
	void clr()
	{
		for(int i = 0; i <= ptr; i ++)
		{
			sub[i] = 0;
			for(int j = 0; j < sigma; j ++) nxt[j][i] = 0;
		}
		ptr = 0;
	}
	void add(string s)
	{
		int v = 0;
		sub[v] ++;
		for(int i = SZ(s) - 1; ~i; i --)
		{
			int ch = s[i] - 'a';
			if(!nxt[ch][v])
			{
				nxt[ch][v] = ++ptr;
			}
			v = nxt[ch][v];
			sub[v] ++;
			assert(v > 0);
		}
	}
	int query(string s)
	{
		int v = 0;
		for(int i = SZ(s) - 1; ~i; i --)
		{
			int ch = s[i] - 'a';
			if(!nxt[ch][v]) return 0;
			v = nxt[ch][v];
		}
		return sub[v];
	}
} DS;

int n, m, ptr, sum[N], Ans[N], nxt[sigma][N];

vector < int > exact[N], vec[N], Q[N];

string s[N], p[N], q[N];

void add(int id)
{
	int v = 0;
	vec[v].push_back(id);
	sum[v] += SZ(s[id]);
	for(int i = 0; i < SZ(s[id]); i ++)
	{
		int ch = s[id][i] - 'a';
		if(!nxt[ch][v])
		{
			nxt[ch][v] = ++ptr;
		}
		v = nxt[ch][v];
		sum[v] += SZ(s[id]);
		vec[v].push_back(id);
	}
	exact[v].push_back(id);
}

int query(int id)
{
	int v = 0;
	for(int i = 0; i < SZ(p[id]); i ++)
	{
		int ch = p[id][i] - 'a';
		if(!nxt[ch][v]) return -1;
		v = nxt[ch][v];
	}
	return v;
}

bool cmp(int i, int j)
{
	return sum[i] > sum[j];
}

void dfs(int v)
{
	vector < int > nei;
	for(int i = 0; i < sigma; i ++)
	{
		if(nxt[i][v])
		{
			nei.push_back(nxt[i][v]);
		}
	}
	sort(all(nei), cmp);
	for(int i = 1; i < SZ(nei); i ++)
	{
		dfs(nei[i]);
		DS.clr();
	}
	if(SZ(nei))
	{
		dfs(nei[0]);
	}
	for(int i = 1; i < SZ(nei); i ++)
	{
		int u = nei[i];
		for(auto id : vec[u])
		{
			DS.add(s[id]);
		}
	}
	for(auto id : exact[v])
	{
		DS.add(s[id]);
	}
	for(auto id : Q[v])
	{
		Ans[id] = DS.query(q[id]);
	}
}

inline int calc(char c)
{
	if(c == 'A') return 0;
	if(c == 'U') return 1;
	if(c == 'C') return 2;
	return 3;
}

int main()
{
	fast_io;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		cin >> s[i];
		for(int j = 0; j < SZ(s[i]); j ++)
		{
			s[i][j] = 'a' + calc(s[i][j]);
		}
		add(i);
	}
	/*for(int i = 0; i <= ptr; i ++)
	{
		for(int j = 0; j < sigma; j ++)
		{
			printf("i = %d j = %d nxt = %d sum = %d\n", i, j, nxt[j][i], sum[i]);
		}
	}
	*/
	for(int i = 1; i <= m; i ++)
	{
		cin >> p[i] >> q[i];
		for(int j = 0; j < SZ(p[i]); j ++)
		{
			p[i][j] = 'a' + calc(p[i][j]);
		}
		for(int j = 0; j < SZ(q[i]); j ++)
		{
			q[i][j] = 'a' + calc(q[i][j]);
		}
		int id = query(i);
		if(id != -1)
		{
			Q[id].push_back(i);
		}
	}
	dfs(0);
	for(int i = 1; i <= m; i ++)
	{
		cout << Ans[i] << endl;
	}
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 329172 KB Output is correct
2 Correct 167 ms 329156 KB Output is correct
3 Correct 175 ms 329176 KB Output is correct
4 Correct 176 ms 329060 KB Output is correct
5 Correct 168 ms 329156 KB Output is correct
6 Correct 167 ms 329168 KB Output is correct
7 Correct 168 ms 329136 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 388788 KB Output is correct
2 Correct 278 ms 385396 KB Output is correct
3 Correct 529 ms 436944 KB Output is correct
4 Correct 493 ms 431808 KB Output is correct
5 Correct 411 ms 420708 KB Output is correct
6 Correct 414 ms 421868 KB Output is correct
7 Correct 254 ms 349312 KB Output is correct
8 Correct 373 ms 386052 KB Output is correct
9 Correct 373 ms 384792 KB Output is correct
10 Correct 359 ms 376560 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 331320 KB Output is correct
2 Correct 184 ms 330924 KB Output is correct
3 Correct 187 ms 331164 KB Output is correct
4 Correct 180 ms 330744 KB Output is correct
5 Correct 188 ms 330920 KB Output is correct
6 Correct 191 ms 331140 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 329172 KB Output is correct
2 Correct 167 ms 329156 KB Output is correct
3 Correct 175 ms 329176 KB Output is correct
4 Correct 176 ms 329060 KB Output is correct
5 Correct 168 ms 329156 KB Output is correct
6 Correct 167 ms 329168 KB Output is correct
7 Correct 168 ms 329136 KB Output is correct
8 Correct 278 ms 388788 KB Output is correct
9 Correct 278 ms 385396 KB Output is correct
10 Correct 529 ms 436944 KB Output is correct
11 Correct 493 ms 431808 KB Output is correct
12 Correct 411 ms 420708 KB Output is correct
13 Correct 414 ms 421868 KB Output is correct
14 Correct 254 ms 349312 KB Output is correct
15 Correct 373 ms 386052 KB Output is correct
16 Correct 373 ms 384792 KB Output is correct
17 Correct 359 ms 376560 KB Output is correct
18 Correct 190 ms 331320 KB Output is correct
19 Correct 184 ms 330924 KB Output is correct
20 Correct 187 ms 331164 KB Output is correct
21 Correct 180 ms 330744 KB Output is correct
22 Correct 188 ms 330920 KB Output is correct
23 Correct 191 ms 331140 KB Output is correct
24 Correct 285 ms 380228 KB Output is correct
25 Correct 306 ms 380948 KB Output is correct
26 Correct 281 ms 379644 KB Output is correct
27 Correct 508 ms 419100 KB Output is correct
28 Correct 352 ms 354392 KB Output is correct
29 Correct 270 ms 339504 KB Output is correct