oj.uz

Submission #245556

# Submission time Handle Problem Language Result Execution time Memory
245556 2020-07-06T18:11:03 Z ruler Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 295 ms 287380 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[N], C[M][SGM], W[M], ST[N], FN[N], 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 99 ms 135416 KB Output is correct
2 Correct 82 ms 135416 KB Output is correct
3 Correct 98 ms 135420 KB Output is correct
4 Correct 87 ms 135416 KB Output is correct
5 Correct 83 ms 135416 KB Output is correct
6 Correct 83 ms 135416 KB Output is correct
7 Correct 81 ms 135416 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 295 ms 287380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 137576 KB Output is correct
2 Correct 96 ms 137080 KB Output is correct
3 Correct 100 ms 137460 KB Output is correct
4 Correct 97 ms 137080 KB Output is correct
5 Correct 98 ms 136952 KB Output is correct
6 Correct 106 ms 137336 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 135416 KB Output is correct
2 Correct 82 ms 135416 KB Output is correct
3 Correct 98 ms 135420 KB Output is correct
4 Correct 87 ms 135416 KB Output is correct
5 Correct 83 ms 135416 KB Output is correct
6 Correct 83 ms 135416 KB Output is correct
7 Correct 81 ms 135416 KB Output is correct
8 Runtime error 295 ms 287380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -