oj.uz

Submission #552036

# Submission time Handle Problem Language Result Execution time Memory
552036 2022-04-22T09:07:47 Z Arnch Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 574896 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 2e6 + 10, mod = 1e9 + 7, A = 30;

void addtrie(string x, int pos);

int n, m, sz, nxt[N][A], nxt2[N][A], ans[N], cnt[N], sz2;
string s[N], t[N][2];
vector<int> ind[N], ind2[N];

inline void get_input() {
	cin >>n >>m;
	for(int i = 0; i < n; i++) {
		cin >>s[i];
		addtrie(s[i], i);
	}
	for(int i = 0; i < m; i++) cin >>t[i][0] >>t[i][1];
}

inline void addtrie(string x, int pos) {
	int p = 0;
	for(int i = 0; i < Sz(x); i++) {
		if(nxt[p][x[i] - 'A']) p = nxt[p][x[i] - 'A'];
		else p = nxt[p][x[i] - 'A'] = ++sz;
	}
	p = 0;
	for(int i = Sz(x) - 1; i >= 0; i--) {
		if(nxt2[p][x[i] - 'A']) p = nxt2[p][x[i] - 'A'];
		else p = nxt2[p][x[i] - 'A'] = ++sz2;
	}
}

inline void dojob(int x) {
	int p = 0;
	for(int i = 0; i < Sz(t[x][0]); i++) {
		if(!nxt[p][t[x][0][i] - 'A']) return;
		p = nxt[p][t[x][0][i] - 'A'];
	}
	ind[p].push_back(x);
	p = 0;
	for(int i = Sz(t[x][1]) - 1; i >= 0; i--) {
		if(!nxt2[p][t[x][1][i] - 'A']) return;
		p = nxt2[p][t[x][1][i] - 'A'];
	}
	ind2[p].push_back(x);
}


inline void call(int pos) {
	vector<int> st;
	int p = 0;
	for(int i = 0; i < Sz(s[pos]); i++) {
		p = nxt[p][s[pos][i] - 'A'];
		for(auto j : ind[p]) {
			cnt[j]++;
			st.push_back(j);
		}
	}
	p = 0;
	for(int i = Sz(s[pos]) - 1; i >= 0; i--) {
		p = nxt2[p][s[pos][i] - 'A'];
		for(auto j : ind2[p]) {
			cnt[j]++;
			if(cnt[j] == 2) ans[j]++;
			st.push_back(j);
		}
	}
	for(auto i : st) cnt[i] = 0;
	st.clear();
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	get_input();

	for(int i = 0; i < m; i++) {
		dojob(i);
	}

	for(int i = 0; i < n; i++) {
		call(i);
	}

	for(int i = 0; i < m; i++) {
		cout<<ans[i] <<endl;
	}


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 282172 KB Output is correct
2 Correct 123 ms 282284 KB Output is correct
3 Correct 119 ms 282140 KB Output is correct
4 Correct 122 ms 282136 KB Output is correct
5 Correct 122 ms 282060 KB Output is correct
6 Correct 123 ms 282084 KB Output is correct
7 Correct 124 ms 282152 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 517860 KB Output is correct
2 Correct 413 ms 505540 KB Output is correct
3 Correct 397 ms 514556 KB Output is correct
4 Correct 423 ms 503336 KB Output is correct
5 Correct 350 ms 570712 KB Output is correct
6 Correct 348 ms 574896 KB Output is correct
7 Correct 283 ms 288556 KB Output is correct
8 Correct 320 ms 456344 KB Output is correct
9 Correct 303 ms 429064 KB Output is correct
10 Correct 571 ms 422324 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 283960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 282172 KB Output is correct
2 Correct 123 ms 282284 KB Output is correct
3 Correct 119 ms 282140 KB Output is correct
4 Correct 122 ms 282136 KB Output is correct
5 Correct 122 ms 282060 KB Output is correct
6 Correct 123 ms 282084 KB Output is correct
7 Correct 124 ms 282152 KB Output is correct
8 Correct 338 ms 517860 KB Output is correct
9 Correct 413 ms 505540 KB Output is correct
10 Correct 397 ms 514556 KB Output is correct
11 Correct 423 ms 503336 KB Output is correct
12 Correct 350 ms 570712 KB Output is correct
13 Correct 348 ms 574896 KB Output is correct
14 Correct 283 ms 288556 KB Output is correct
15 Correct 320 ms 456344 KB Output is correct
16 Correct 303 ms 429064 KB Output is correct
17 Correct 571 ms 422324 KB Output is correct
18 Execution timed out 1542 ms 283960 KB Time limit exceeded
19 Halted 0 ms 0 KB -