oj.uz

Submission #122924

# Submission time Handle Problem Language Result Execution time Memory
122924 2019-06-29T14:42:20 Z egorlifar Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 190660 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);
	}
	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;
			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);
			}
		}
	}
	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 104 ms 113528 KB Output is correct
2 Correct 102 ms 113528 KB Output is correct
3 Correct 116 ms 113620 KB Output is correct
4 Correct 107 ms 113528 KB Output is correct
5 Correct 103 ms 113528 KB Output is correct
6 Correct 104 ms 113528 KB Output is correct
7 Correct 103 ms 113528 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 120308 KB Output is correct
2 Correct 173 ms 120184 KB Output is correct
3 Correct 662 ms 160632 KB Output is correct
4 Correct 717 ms 160132 KB Output is correct
5 Execution timed out 1569 ms 190660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 114936 KB Output is correct
2 Correct 114 ms 114596 KB Output is correct
3 Correct 116 ms 114880 KB Output is correct
4 Correct 111 ms 114424 KB Output is correct
5 Correct 117 ms 114916 KB Output is correct
6 Correct 120 ms 114936 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 113528 KB Output is correct
2 Correct 102 ms 113528 KB Output is correct
3 Correct 116 ms 113620 KB Output is correct
4 Correct 107 ms 113528 KB Output is correct
5 Correct 103 ms 113528 KB Output is correct
6 Correct 104 ms 113528 KB Output is correct
7 Correct 103 ms 113528 KB Output is correct
8 Correct 170 ms 120308 KB Output is correct
9 Correct 173 ms 120184 KB Output is correct
10 Correct 662 ms 160632 KB Output is correct
11 Correct 717 ms 160132 KB Output is correct
12 Execution timed out 1569 ms 190660 KB Time limit exceeded
13 Halted 0 ms 0 KB -