제출 #1208423

#제출 시각아이디문제언어결과실행 시간메모리
1208423minhpkSelling RNA Strands (JOI16_selling_rna)C++20
35 / 100
512 ms453884 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a, q; int child[2000005][26]; string z[100005]; int cnt, markNode[1000005], sta[1000005], finNode[1000005], tour; vector<pair<long long, int>> allPairs; const int BASE = 31; void add(const string &s, int idx) { int u = 0; for (char c : s) { int d = c - 'A'; if (!child[u][d]) child[u][d] = ++cnt; u = child[u][d]; } markNode[idx] = u; } void dfs(int u) { sta[u] = ++tour; for (int d = 0; d < 26; ++d) { int v = child[u][d]; if (v) dfs(v); } finNode[u] = tour; } int getCount(const string &pre, long long hq) { int u = 0; for (char c : pre) { int d = c - 'A'; if (!child[u][d]) return 0; u = child[u][d]; } int L = sta[u], R = finNode[u]; auto lo = lower_bound(allPairs.begin(), allPairs.end(), make_pair(hq, -1LL)); auto hi = upper_bound(allPairs.begin(), allPairs.end(), make_pair(hq, (int)1e9)); if (lo == hi) return 0; auto it1 = lower_bound(lo, hi, make_pair(hq, L)); auto it2 = upper_bound(lo, hi, make_pair(hq, R)); return it2 - it1; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> a >> q; for (int i = 1; i <= a; ++i) { cin >> z[i]; add(z[i], i); } dfs(0); long long totalLen = 0; for (int i = 1; i <= a; ++i) totalLen += z[i].size(); allPairs.reserve(totalLen); for (int i = 1; i <= a; ++i) { long long h = 0; int pos = sta[markNode[i]]; for (int j = z[i].size() - 1; j >= 0; --j) { h = h * BASE + (z[i][j] - 'A' + 1); allPairs.emplace_back(h, pos); } } sort(allPairs.begin(), allPairs.end()); while (q--) { string P, Q; cin >> P >> Q; long long hq = 0; for (int j = Q.size() - 1; j >= 0; --j) hq = hq * BASE + (Q[j] - 'A' + 1); cout << getCount(P, hq) << '\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...