oj.uz

Submission #122913

# Submission time Handle Problem Language Result Execution time Memory
122913 2019-06-29T14:33:11 Z egorlifar Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 199120 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 100001;
const int Mod = 1000000007;
const int P = 424243;


int sum(int a, int b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}


int mul(int a, int b) {
	return (1LL * a * b) % Mod;
}

int n, m;
int nxt[MAXN * 22][4];
int where[MAXN];
int uk = 1;
string s[MAXN], p[MAXN], q[MAXN];
bool good[MAXN];
int ps[MAXN];
vector<pair<int, int> > g[MAXN * 22];
int ans[MAXN];
vector<int> ft[MAXN * 22];


int get(char c) {
	if (c == 'A') {
		return 0;
	}
	if (c == 'G') {
		return 1;
	}
	if (c == 'U') {
		return 2;
	}
	return 3;
}



void add(string s, int f) {
	int cur = 0;
	for (auto x: s) {
		int f = nxt[cur][get(x)];
		if (f) {
			cur = f;
		} else {
			nxt[cur][get(x)] = uk;
			cur = uk;
			uk++;
		}
	}
	where[f] = cur;
}



void dfs(int u, map<int, int> &cnt) {
	for (auto x: ft[u]) {
		cnt[x]++;
	}
	for (int t = 0; t < 4; t++) {
		if (!nxt[u][t]) {
			continue;
		}
		int h = nxt[u][t];
		map<int, int> cnt1;
		dfs(h, cnt1);
		if (sz(cnt) < sz(cnt1)) {
			swap(cnt, cnt1);
		}
		for (auto x: cnt1) {
			cnt[x.first] += x.second;
		}
	}
	for (auto y: g[u]) {
		ans[y.first] += (cnt.find(y.second) == cnt.end() ? 0: cnt.at(y.second));
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		add(s[i], i);
	}
	ps[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		ps[i] = mul(ps[i - 1], P);
	}
	for (int i = 0; i < m; i++) {
		cin >> p[i] >> q[i];
		good[sz(q[i])] = true;
		int cur = 0;
		bool bad = false;
		for (auto x: p[i]) {
			if (!nxt[cur][get(x)]) {
				bad = true;
			} else {
				cur = nxt[cur][get(x)];
			}
		}
		int hsh = 0;
		for (auto x: q[i]) {
			hsh = sum(mul(hsh, P), get(x) + 1);
		}
		//cout << hsh << endl;
		if (!bad) {
			//cout << i + 1 << endl;
			g[cur].pb({i, hsh});
		}
	}
	for (int i = 0; i < n; i++) {
		int cur = 0;
		for (int j = sz(s[i]) - 1; j >= 0; j--) {
			cur = sum(cur, mul(get(s[i][j]) + 1, ps[sz(s[i]) - j - 1]));
			//cout << cur << endl;
			if (good[sz(s[i]) - j]) {
				ft[where[i]].pb(cur);
			}
		}
	}
	map<int, int> cnt;
	dfs(0, cnt);
	for (int i = 0; i < m; i++) {
		cout << ans[i] << '\n';
	}
	return 0; 		
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 113400 KB Output is correct
2 Correct 114 ms 113528 KB Output is correct
3 Correct 114 ms 113500 KB Output is correct
4 Correct 103 ms 113400 KB Output is correct
5 Correct 101 ms 113404 KB Output is correct
6 Correct 104 ms 113588 KB Output is correct
7 Correct 103 ms 113516 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 119288 KB Output is correct
2 Correct 147 ms 119024 KB Output is correct
3 Correct 712 ms 159356 KB Output is correct
4 Correct 767 ms 158788 KB Output is correct
5 Execution timed out 1577 ms 199120 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 115284 KB Output is correct
2 Correct 121 ms 114800 KB Output is correct
3 Correct 131 ms 115092 KB Output is correct
4 Correct 139 ms 114680 KB Output is correct
5 Correct 124 ms 115100 KB Output is correct
6 Correct 125 ms 115192 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 113400 KB Output is correct
2 Correct 114 ms 113528 KB Output is correct
3 Correct 114 ms 113500 KB Output is correct
4 Correct 103 ms 113400 KB Output is correct
5 Correct 101 ms 113404 KB Output is correct
6 Correct 104 ms 113588 KB Output is correct
7 Correct 103 ms 113516 KB Output is correct
8 Correct 147 ms 119288 KB Output is correct
9 Correct 147 ms 119024 KB Output is correct
10 Correct 712 ms 159356 KB Output is correct
11 Correct 767 ms 158788 KB Output is correct
12 Execution timed out 1577 ms 199120 KB Time limit exceeded
13 Halted 0 ms 0 KB -