제출 #122913

#제출 시각아이디문제언어결과실행 시간메모리
122913egorlifarSelling RNA Strands (JOI16_selling_rna)C++17
35 / 100
1577 ms199120 KiB
/* ЗАПУСКАЕМ ░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░ ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░ */ #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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...