제출 #1195941

#제출 시각아이디문제언어결과실행 시간메모리
1195941KindaGoodGamesSelling RNA Strands (JOI16_selling_rna)C++20
0 / 100
1004 ms1114112 KiB
// #pragma GCC optimize("O3,unroll-loops,Ofast") // #pragma GCC target("avx2") #include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pcc pair<char,char> #define tiii tuple<int,int,int> using namespace std; int conv(char c){ if(c == 'A') return 0; if(c == 'G') return 1; if(c == 'C') return 2; else return 3; } struct TrieNodePr{ int marked = false; vector<vector<int>> child; int markedSub = 0; TrieNodePr(){ child.resize(4, vector<int>(4, -1)); } }; struct TrieNode{ int marked = false; vector<int> child; int markedSub = 0; TrieNode(){ child.resize(4, -1); } }; vector<TrieNodePr> triePr(1); vector<TrieNode> trieP(1); vector<TrieNode> trieS(1); void insertPr(string& s, int l, int r, int ind = 0){ if(l == s.size()) { triePr[ind].marked++; triePr[ind].markedSub++; return; } int cl = conv(s[l]); int cr = conv(s[r]); if(triePr[ind].child[cl][cr] == -1){ triePr[ind].child[cl][cr] = triePr.size(); triePr.push_back(TrieNodePr()); } int ch = triePr[ind].child[cl][cr]; triePr[ind].markedSub -= triePr[ch].markedSub; insertPr(s,l+1,r-1,triePr[ind].child[cl][cr]); triePr[ind].markedSub += triePr[ch].markedSub; } void insertPr(string& s){ insertPr(s, 0, s.size()-1); } void insertSing(string& s, int i, vector<TrieNode>& trie, int ind = 0){ if(i == s.size()) { triePr[ind].marked++; triePr[ind].markedSub++; return; } int ci = conv(s[i]); if(trie[ind].child[ci] == -1){ trie[ind].child[ci] = trie.size(); trie.push_back(TrieNode()); } int ch = trie[ind].child[ci]; trie[ind].markedSub -= trie[ch].markedSub; insertPr(s,i+1,trie[ind].child[ci]); trie[ind].markedSub += trie[ch].markedSub; } int trav(string& p, string& s, int i, int indP){ if(indP == -1) return 0; if(i == max(p.size(),s.size())){ return triePr[indP].markedSub; } if(i < p.size() && i < s.size()){ int cl = conv(p[i]); int cr = conv(s[i]); int c = triePr[indP].child[cl][cr]; if(c == -1) return 0; return trav(p,s,i+1,c); } if(i < p.size() && i >= s.size()){ int cl = conv(p[i]); int r1 = trav(p,s,i+1,triePr[indP].child[cl][0]); int r2 = trav(p,s,i+1,triePr[indP].child[cl][1]); int r3 = trav(p,s,i+1,triePr[indP].child[cl][2]); int r4 = trav(p,s,i+1,triePr[indP].child[cl][3]); return r1+r2+r3+r4; } if(i >= p.size() && i < s.size()){ int cr = conv(s[i]); int r1 = trav(p,s,i+1,triePr[indP].child[0][cr]); int r2 = trav(p,s,i+1,triePr[indP].child[1][cr]); int r3 = trav(p,s,i+1,triePr[indP].child[2][cr]); int r4 = trav(p,s,i+1,triePr[indP].child[3][cr]); return r1+r2+r3+r4; } // what the flip? assert(false); return 0; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,m; cin >> n >> m; for(int i = 0; i < n; i++){ string s; cin >> s; insertPr(s); insertSing(s, 0, trieP, 0); reverse(s.begin(),s.end()); insertSing(s, 0, trieS, 0); } for(int i =0; i < m; i++){ string p,s; cin >> p >> s; reverse(s.begin(),s.end()); cout << trav(p,s,0,0) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...