# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
748472 | 2023-05-26T10:38:02 Z | guagua0407 | Selling RNA Strands (JOI16_selling_rna) | C++17 | 1144 ms | 537720 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } const int mxn=2e6+5; string S[mxn]; string rev[mxn]; string T1[mxn],T2[mxn]; int trie[mxn][4]; int trie2[mxn][4]; int cnt[mxn*4]; int ans[mxn]; vector<int> query[mxn*4]; map<char,int> mp; map<int,char> mp2; int cur=0; string now=""; bool comp(vector<int> a,vector<int> b){ return a.size()<b.size(); } void insert(string str){ int v=0; for(int i=0;i<str.length();i++){ int a=mp[str[i]]; if(trie[v][a]==-1){ cur++; trie[v][a]=cur; v=cur; } else{ v=trie[v][a]; } } } void insert1(string str,int id){ int v=0; for(int i=0;i<str.length() and v!=-1;i++){ int a=mp[str[i]]; v=trie[v][a]; } if(v!=-1){ query[v].push_back(id); } } void upd(string str,int d){ int v=0; for(int i=0;i<str.length();i++){ int a=mp[str[i]]; if(trie2[v][a]==-1){ cur++; trie2[v][a]=cur; v=cur; } else{ v=trie2[v][a]; } cnt[v]+=d; } } int query2(string str){ int v=0; for(int i=0;i<str.length() and v!=-1;i++){ int a=mp[str[i]]; v=trie2[v][a]; } if(v==-1) return 0; return cnt[v]; } void dfs(int v,vector<int> vec,int ord=0){ vector<int> num[4]; for(auto u:vec){ if(S[u].size()<=ord){ continue; } num[mp[S[u][ord]]].push_back(u); } sort(num,num+4,comp); for(int i=0;i<4;i++){ if(num[i].empty()) continue; int a=mp[S[num[i][0]][ord]]; dfs(trie[v][a],num[i],ord+1); if(i==3) break; for(auto u:num[i]){ upd(rev[u],-1); } } for(int i=0;i<3;i++){ for(auto u:num[i]){ upd(rev[u],1); } } for(auto u:vec){ if(S[u].size()<=ord){ upd(rev[u],1); } } for(auto u:query[v]){ ans[u]=query2(T2[u]); } } int main() {_ mp['A']=0; mp['G']=1; mp['C']=2; mp['U']=3; for(int i=0;i<mxn;i++){ for(int j=0;j<4;j++){ trie[i][j]=trie2[i][j]=-1; } } int n,m; cin>>n>>m; for(int i=0;i<n;i++){ cin>>S[i]; rev[i]=S[i]; reverse(all(rev[i])); insert(S[i]); } for(int i=0;i<m;i++){ cin>>T1[i]>>T2[i]; reverse(all(T2[i])); insert1(T1[i],i); } vector<int> vec(n); for(int i=0;i<n;i++){ vec[i]=i; } dfs(0,vec); for(int i=0;i<m;i++){ cout<<ans[i]<<'\n'; } return 0; } //maybe its multiset not set
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 223 ms | 501208 KB | Output is correct |
2 | Correct | 240 ms | 501428 KB | Output is correct |
3 | Correct | 228 ms | 501300 KB | Output is correct |
4 | Correct | 220 ms | 501240 KB | Output is correct |
5 | Correct | 217 ms | 501276 KB | Output is correct |
6 | Correct | 214 ms | 501264 KB | Output is correct |
7 | Correct | 245 ms | 501188 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 384 ms | 537340 KB | Output is correct |
2 | Correct | 384 ms | 537720 KB | Output is correct |
3 | Correct | 1144 ms | 512712 KB | Output is correct |
4 | Correct | 1107 ms | 512240 KB | Output is correct |
5 | Correct | 811 ms | 515624 KB | Output is correct |
6 | Correct | 824 ms | 515908 KB | Output is correct |
7 | Correct | 296 ms | 528844 KB | Output is correct |
8 | Correct | 555 ms | 524416 KB | Output is correct |
9 | Correct | 523 ms | 525896 KB | Output is correct |
10 | Correct | 587 ms | 521384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 242 ms | 503240 KB | Output is correct |
2 | Correct | 245 ms | 503008 KB | Output is correct |
3 | Correct | 259 ms | 502988 KB | Output is correct |
4 | Correct | 255 ms | 502684 KB | Output is correct |
5 | Correct | 245 ms | 502584 KB | Output is correct |
6 | Correct | 276 ms | 502724 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 223 ms | 501208 KB | Output is correct |
2 | Correct | 240 ms | 501428 KB | Output is correct |
3 | Correct | 228 ms | 501300 KB | Output is correct |
4 | Correct | 220 ms | 501240 KB | Output is correct |
5 | Correct | 217 ms | 501276 KB | Output is correct |
6 | Correct | 214 ms | 501264 KB | Output is correct |
7 | Correct | 245 ms | 501188 KB | Output is correct |
8 | Correct | 384 ms | 537340 KB | Output is correct |
9 | Correct | 384 ms | 537720 KB | Output is correct |
10 | Correct | 1144 ms | 512712 KB | Output is correct |
11 | Correct | 1107 ms | 512240 KB | Output is correct |
12 | Correct | 811 ms | 515624 KB | Output is correct |
13 | Correct | 824 ms | 515908 KB | Output is correct |
14 | Correct | 296 ms | 528844 KB | Output is correct |
15 | Correct | 555 ms | 524416 KB | Output is correct |
16 | Correct | 523 ms | 525896 KB | Output is correct |
17 | Correct | 587 ms | 521384 KB | Output is correct |
18 | Correct | 242 ms | 503240 KB | Output is correct |
19 | Correct | 245 ms | 503008 KB | Output is correct |
20 | Correct | 259 ms | 502988 KB | Output is correct |
21 | Correct | 255 ms | 502684 KB | Output is correct |
22 | Correct | 245 ms | 502584 KB | Output is correct |
23 | Correct | 276 ms | 502724 KB | Output is correct |
24 | Correct | 398 ms | 535980 KB | Output is correct |
25 | Correct | 400 ms | 536924 KB | Output is correct |
26 | Correct | 395 ms | 535692 KB | Output is correct |
27 | Correct | 1000 ms | 512656 KB | Output is correct |
28 | Correct | 458 ms | 531328 KB | Output is correct |
29 | Correct | 352 ms | 509024 KB | Output is correct |