oj.uz

Submission #122925

# Submission time Handle Problem Language Result Execution time Memory
122925 2019-06-29T14:44:07 Z egorlifar Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1051 ms 192328 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 <unordered_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;

/** Interface */
     
inline int readChar();
template <class T = int> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );
     
/** Read */
     
static const int buf_size = 4096;
     
inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len) {
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    }
    if (pos == len) {
        return -1;
    }
    return buf[pos++];
}
     
inline int readChar() {
    int c = getChar();
    while (c <= 32) {
        c = getChar();
    }
    return c;
}


inline string readWord() {
	char c = readChar();
	string kek;
	kek += c;
	while (true) {
		c = getChar();
		if (c <= 32) break;
		kek += c;
	}
	return kek;
}
     
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
     
/** Write */
     
static int write_pos = 0;
static char write_buf[buf_size];
     
inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
     
template <class T> 
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;
     
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
     
inline void writeWord( const char *s ) {     while (*s)
writeChar(*s++); }
     
struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;   
template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(const T &x, ostream &out = cerr) {
	output(x.begin(), x.end(), out);
}
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, unordered_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];
		unordered_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[y.second];
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	n = readInt(), m = readInt();
	for (int i = 0; i < n; i++) {
		s[i] = readWord();
		add(s[i], i);
	}
	ps[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		ps[i] = mul(ps[i - 1], P);
	}
	unordered_map<int, int> was;
	for (int i = 0; i < m; i++) {
			p[i] = readWord(), q[i] = readWord();
		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;
			was[hsh] = true;
			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]) {
				if (was[cur]) {
					ft[where[i]].pb(cur);
				}
			}
		}
	}
	unordered_map<int, int> cnt;
	dfs(0, cnt);
	for (int i = 0; i < m; i++) {
		writeInt(ans[i], '\n');
	}
	return 0; 		
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 113528 KB Output is correct
2 Correct 103 ms 113448 KB Output is correct
3 Correct 104 ms 113528 KB Output is correct
4 Correct 107 ms 113500 KB Output is correct
5 Correct 102 ms 113428 KB Output is correct
6 Correct 101 ms 113528 KB Output is correct
7 Correct 101 ms 113400 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 120376 KB Output is correct
2 Correct 173 ms 120184 KB Output is correct
3 Correct 688 ms 160592 KB Output is correct
4 Correct 760 ms 160224 KB Output is correct
5 Correct 1028 ms 188912 KB Output is correct
6 Correct 1051 ms 192328 KB Output is correct
7 Correct 523 ms 189472 KB Output is correct
8 Correct 257 ms 138488 KB Output is correct
9 Correct 256 ms 137212 KB Output is correct
10 Correct 274 ms 133624 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 115192 KB Output is correct
2 Correct 124 ms 114780 KB Output is correct
3 Correct 121 ms 114960 KB Output is correct
4 Correct 115 ms 114688 KB Output is correct
5 Correct 120 ms 114780 KB Output is correct
6 Correct 121 ms 114936 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 113528 KB Output is correct
2 Correct 103 ms 113448 KB Output is correct
3 Correct 104 ms 113528 KB Output is correct
4 Correct 107 ms 113500 KB Output is correct
5 Correct 102 ms 113428 KB Output is correct
6 Correct 101 ms 113528 KB Output is correct
7 Correct 101 ms 113400 KB Output is correct
8 Correct 169 ms 120376 KB Output is correct
9 Correct 173 ms 120184 KB Output is correct
10 Correct 688 ms 160592 KB Output is correct
11 Correct 760 ms 160224 KB Output is correct
12 Correct 1028 ms 188912 KB Output is correct
13 Correct 1051 ms 192328 KB Output is correct
14 Correct 523 ms 189472 KB Output is correct
15 Correct 257 ms 138488 KB Output is correct
16 Correct 256 ms 137212 KB Output is correct
17 Correct 274 ms 133624 KB Output is correct
18 Correct 120 ms 115192 KB Output is correct
19 Correct 124 ms 114780 KB Output is correct
20 Correct 121 ms 114960 KB Output is correct
21 Correct 115 ms 114688 KB Output is correct
22 Correct 120 ms 114780 KB Output is correct
23 Correct 121 ms 114936 KB Output is correct
24 Correct 213 ms 124900 KB Output is correct
25 Correct 228 ms 125928 KB Output is correct
26 Correct 186 ms 124408 KB Output is correct
27 Correct 635 ms 158348 KB Output is correct
28 Correct 247 ms 128632 KB Output is correct
29 Correct 165 ms 119416 KB Output is correct