Submission #528826

#TimeUsernameProblemLanguageResultExecution timeMemory
528826AriaHSelling RNA Strands (JOI16_selling_rna)C++17
100 / 100
529 ms436944 KiB
/* I can do this all day */ #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(),x.end() #define Mp make_pair #define point complex #define endl '\n' #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout); #define mashtali return cout << "Hello, World!", 0; const int N = 2e6 + 10; const int LOG = 20; const ll mod = 1e9 + 7; const ll inf = 8e18; const double pi = acos(-1); const ld eps = 1e-18; const ld one = 1.; const int sigma = 4; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } mt19937 rng(time(nullptr)); struct Trie { int ptr, sub[N], nxt[sigma][N]; void clr() { for(int i = 0; i <= ptr; i ++) { sub[i] = 0; for(int j = 0; j < sigma; j ++) nxt[j][i] = 0; } ptr = 0; } void add(string s) { int v = 0; sub[v] ++; for(int i = SZ(s) - 1; ~i; i --) { int ch = s[i] - 'a'; if(!nxt[ch][v]) { nxt[ch][v] = ++ptr; } v = nxt[ch][v]; sub[v] ++; assert(v > 0); } } int query(string s) { int v = 0; for(int i = SZ(s) - 1; ~i; i --) { int ch = s[i] - 'a'; if(!nxt[ch][v]) return 0; v = nxt[ch][v]; } return sub[v]; } } DS; int n, m, ptr, sum[N], Ans[N], nxt[sigma][N]; vector < int > exact[N], vec[N], Q[N]; string s[N], p[N], q[N]; void add(int id) { int v = 0; vec[v].push_back(id); sum[v] += SZ(s[id]); for(int i = 0; i < SZ(s[id]); i ++) { int ch = s[id][i] - 'a'; if(!nxt[ch][v]) { nxt[ch][v] = ++ptr; } v = nxt[ch][v]; sum[v] += SZ(s[id]); vec[v].push_back(id); } exact[v].push_back(id); } int query(int id) { int v = 0; for(int i = 0; i < SZ(p[id]); i ++) { int ch = p[id][i] - 'a'; if(!nxt[ch][v]) return -1; v = nxt[ch][v]; } return v; } bool cmp(int i, int j) { return sum[i] > sum[j]; } void dfs(int v) { vector < int > nei; for(int i = 0; i < sigma; i ++) { if(nxt[i][v]) { nei.push_back(nxt[i][v]); } } sort(all(nei), cmp); for(int i = 1; i < SZ(nei); i ++) { dfs(nei[i]); DS.clr(); } if(SZ(nei)) { dfs(nei[0]); } for(int i = 1; i < SZ(nei); i ++) { int u = nei[i]; for(auto id : vec[u]) { DS.add(s[id]); } } for(auto id : exact[v]) { DS.add(s[id]); } for(auto id : Q[v]) { Ans[id] = DS.query(q[id]); } } inline int calc(char c) { if(c == 'A') return 0; if(c == 'U') return 1; if(c == 'C') return 2; return 3; } int main() { fast_io; cin >> n >> m; for(int i = 1; i <= n; i ++) { cin >> s[i]; for(int j = 0; j < SZ(s[i]); j ++) { s[i][j] = 'a' + calc(s[i][j]); } add(i); } /*for(int i = 0; i <= ptr; i ++) { for(int j = 0; j < sigma; j ++) { printf("i = %d j = %d nxt = %d sum = %d\n", i, j, nxt[j][i], sum[i]); } } */ for(int i = 1; i <= m; i ++) { cin >> p[i] >> q[i]; for(int j = 0; j < SZ(p[i]); j ++) { p[i][j] = 'a' + calc(p[i][j]); } for(int j = 0; j < SZ(q[i]); j ++) { q[i][j] = 'a' + calc(q[i][j]); } int id = query(i); if(id != -1) { Q[id].push_back(i); } } dfs(0); for(int i = 1; i <= m; i ++) { cout << Ans[i] << endl; } return 0; } /* check corner case(n = 1?), watch for negetive index or overflow */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...