oj.uz

Submission #245561

# Submission time Handle Problem Language Result Execution time Memory
245561 2020-07-06T18:20:57 Z ruler Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 234 ms 170104 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////
 
const int N = 1e5 + 5, M = 2e6 + 5, SGM = 4;
 
int t, clk, CNT[M], C[M][SGM], W[M], ST[M], FN[M], ANS[N];
string S[N], PRE[N], SUF[N];
vector<pii> Q[M];
vector<int> Z[M];
 
int Add(string &s) {
	int now = 0;
	for (char c : s) {
		if (!C[now][c - 'A']) C[now][c - 'A'] = ++t;
		now = C[now][c - 'A'];
		CNT[now]++;
	}
	return now;
}
void Compress(string &s) {
	for (char &c : s) {
		if (c == 'G') c = 'B';
		if (c == 'U') c = 'D';
	}
}
void DFS(int v) {
	ST[v] = clk++, W[ST[v]] = v;
	for (int i = 0; i < SGM; i++) if (C[v][i]) DFS(C[v][i]);
	FN[v] = clk;
}
 
int main() {
 
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> S[i]; Compress(S[i]);
		int node = Add(S[i]);
		Z[node].push_back(i);
	}
	DFS(0);
	for (int i = 0; i < q; i++) {
		cin >> PRE[i] >> SUF[i]; Compress(PRE[i]), Compress(SUF[i]);
		int now = 0;
		for (char c : PRE[i]) {
			now = C[now][c - 'A'];
			if (!now) break;
		}
		if (now == 0) continue;
		reverse(all(SUF[i]));
		Q[ST[now]].push_back(make_pair(-1, i));
		Q[FN[now]].push_back(make_pair(+1, i));
	}
	memset(C, 0, sizeof C), memset(CNT, 0, sizeof CNT), t = 0;
	for (int i = 0; i < n; i++) reverse(all(S[i]));
	for (int i = 0; i <= clk; i++) {
		for (pii p : Q[i]) {
			int now = 0;
			for (char c : SUF[p.second]) {
				now = C[now][c - 'A'];
				if (!now) break;
			}
			if (now == 0) continue;
			ANS[p.second] += p.first * CNT[now];
		}
		for (int j : Z[W[i]]) Add(S[j]);
	}
	for (int i = 0; i < q; i++) cout << ANS[i] << endl;
	
 
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 142840 KB Output is correct
2 Correct 89 ms 142844 KB Output is correct
3 Correct 88 ms 142840 KB Output is correct
4 Correct 86 ms 142840 KB Output is correct
5 Correct 93 ms 142832 KB Output is correct
6 Correct 86 ms 142840 KB Output is correct
7 Correct 85 ms 142840 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 147480 KB Output is correct
2 Correct 159 ms 147452 KB Output is correct
3 Correct 221 ms 170104 KB Output is correct
4 Correct 202 ms 168952 KB Output is correct
5 Correct 188 ms 160284 KB Output is correct
6 Correct 190 ms 160508 KB Output is correct
7 Correct 145 ms 148856 KB Output is correct
8 Correct 185 ms 157816 KB Output is correct
9 Correct 177 ms 156408 KB Output is correct
10 Correct 151 ms 153776 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 144620 KB Output is correct
2 Correct 103 ms 144120 KB Output is correct
3 Correct 107 ms 144504 KB Output is correct
4 Correct 114 ms 144120 KB Output is correct
5 Correct 107 ms 143992 KB Output is correct
6 Correct 127 ms 144248 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 142840 KB Output is correct
2 Correct 89 ms 142844 KB Output is correct
3 Correct 88 ms 142840 KB Output is correct
4 Correct 86 ms 142840 KB Output is correct
5 Correct 93 ms 142832 KB Output is correct
6 Correct 86 ms 142840 KB Output is correct
7 Correct 85 ms 142840 KB Output is correct
8 Correct 153 ms 147480 KB Output is correct
9 Correct 159 ms 147452 KB Output is correct
10 Correct 221 ms 170104 KB Output is correct
11 Correct 202 ms 168952 KB Output is correct
12 Correct 188 ms 160284 KB Output is correct
13 Correct 190 ms 160508 KB Output is correct
14 Correct 145 ms 148856 KB Output is correct
15 Correct 185 ms 157816 KB Output is correct
16 Correct 177 ms 156408 KB Output is correct
17 Correct 151 ms 153776 KB Output is correct
18 Correct 108 ms 144620 KB Output is correct
19 Correct 103 ms 144120 KB Output is correct
20 Correct 107 ms 144504 KB Output is correct
21 Correct 114 ms 144120 KB Output is correct
22 Correct 107 ms 143992 KB Output is correct
23 Correct 127 ms 144248 KB Output is correct
24 Correct 164 ms 148216 KB Output is correct
25 Correct 164 ms 149372 KB Output is correct
26 Correct 164 ms 147704 KB Output is correct
27 Correct 208 ms 166392 KB Output is correct
28 Correct 234 ms 152056 KB Output is correct
29 Correct 157 ms 146168 KB Output is correct