oj.uz

Submission #122917

# Submission time Handle Problem Language Result Execution time Memory
122917 2019-06-29T14:35:41 Z egorlifar Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 200012 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;

/** 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, 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[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);
			}
		}
	}
	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 102 ms 113528 KB Output is correct
2 Correct 104 ms 113532 KB Output is correct
3 Correct 104 ms 113580 KB Output is correct
4 Correct 104 ms 113528 KB Output is correct
5 Correct 103 ms 113528 KB Output is correct
6 Correct 105 ms 113508 KB Output is correct
7 Correct 104 ms 113528 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 120480 KB Output is correct
2 Correct 176 ms 120132 KB Output is correct
3 Correct 727 ms 160816 KB Output is correct
4 Correct 791 ms 160304 KB Output is correct
5 Execution timed out 1588 ms 200012 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 114936 KB Output is correct
2 Correct 114 ms 114468 KB Output is correct
3 Correct 116 ms 114808 KB Output is correct
4 Correct 111 ms 114396 KB Output is correct
5 Correct 115 ms 114808 KB Output is correct
6 Correct 116 ms 114936 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 113528 KB Output is correct
2 Correct 104 ms 113532 KB Output is correct
3 Correct 104 ms 113580 KB Output is correct
4 Correct 104 ms 113528 KB Output is correct
5 Correct 103 ms 113528 KB Output is correct
6 Correct 105 ms 113508 KB Output is correct
7 Correct 104 ms 113528 KB Output is correct
8 Correct 187 ms 120480 KB Output is correct
9 Correct 176 ms 120132 KB Output is correct
10 Correct 727 ms 160816 KB Output is correct
11 Correct 791 ms 160304 KB Output is correct
12 Execution timed out 1588 ms 200012 KB Time limit exceeded
13 Halted 0 ms 0 KB -