Submission #112655

#TimeUsernameProblemLanguageResultExecution timeMemory
112655MladenPSelling RNA Strands (JOI16_selling_rna)C++17
0 / 100
43 ms49792 KiB
#include<bits/stdc++.h> #define STIZE(x) fprintf(stderr, "STIZE%d\n", x); #define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x); #define NL(x) printf("%c", " \n"[(x)]); #define lld long long #define pii pair<int,int> #define pb push_back #define fi first #define se second #define mid (l+r)/2 #define endl '\n' #define all(a) begin(a),end(a) #define sz(a) int((a).size()) #define LINF 1000000000000000LL #define INF 1000000000 #define EPS 1e-9 using namespace std; #define MAXL 2000000 #define MAXN 100010 #define MOD 29996224275833LL int trie[MAXL][4], siz[MAXL], idx[MAXL], nodes, timer, hshidx, key, f[300], F[300], stf[MAXN][4]; bool sorted[MAXL]; vector<int> gde[MAXL]; unordered_map<int,int> cudo, celi; lld hsh[MAXN], hsh1[MAXN], st[MAXN]; char P[MAXN], Q[MAXN], S[MAXN]; void ubaci(char s[], int len) { int node = 0; for(int idx = 0; idx < len; idx++) { int c = f[s[idx]]; if(trie[node][c] == 0) trie[node][c] = ++nodes; //inNode[node].pb(hsh[len-1-idx]); gde[hsh[len-1-idx]].pb(node); node = trie[node][c]; } } stack<int> dfsq; int DFS(int node) { dfsq.push(node); while(!dfsq.empty()) { int top = dfsq.top(); if(idx[top] == 0) { idx[top] = ++timer; //for(auto x : inNode[top]) gde[x].pb(idx[top]); for(int i = 0; i < 4; i++) if(trie[top][i]) dfsq.push(trie[top][i]); } else { dfsq.pop(); siz[top] = 1; for(int i = 0; i < 4; i++) if(trie[top][i]) siz[top] += siz[trie[top][i]]; } } } void hashuj(char s[], lld hsh[], int lens) { fill(hsh, hsh+lens+5, 0); for(int i = 0; i < lens; i++) { hsh[i] += stf[i][f[s[i]]]; if(hsh[i] >= MOD) hsh[i] %= MOD; //hsh[i+1] += hsh[i]; if(i == lens-1) celi[hsh[i]]++; else hsh[i+1] += hsh[i]; int x = cudo[hsh[i]]; if(x == 0) cudo[hsh[i]] = ++hshidx, hsh[i] = hshidx; else hsh[i] = x; } } void hashuj1(char s[], lld hsh[], int lens) { fill(hsh, hsh+lens+5, 0); for(int i = 0; i < lens; i++) { hsh[i] += stf[i][f[s[i]]]; if(hsh[i] >= MOD) hsh[i] %= MOD; hsh[i+1] += hsh[i]; } } int query(char s[], int len) { int node = 0; for(int idxx = 0; idxx < len; idxx++) { int c = f[s[idxx]]; if(trie[node][c] == 0) return -1; node = trie[node][c]; } return node; } int main() { freopen("02-01.txt", "r", stdin); freopen("out.txt", "w", stdout); int N, M; scanf("%d%d", &N, &M); f['A'] = 0, f['G'] = 1, f['C'] = 2, f['U'] = 3, st[0] = 1; F['A'] = 1, F['G'] = 2, F['C'] = 3, F['U'] = 4; for(int i = 1; i < MAXN; i++) st[i] = (st[i-1]*5 >= MOD ? (st[i-1]*5)%MOD : st[i-1]*5); stf[0][0] = F['A']; stf[0][1] = F['G']; stf[0][2] = F['C']; stf[0][3] = F['U']; for(int i = 1; i < MAXN; i++) { stf[i][0] = (stf[i-1][0]*5 >= MOD ? (stf[i-1][0]*5)%MOD : stf[i-1][0]*5); stf[i][1] = (stf[i-1][1]*5 >= MOD ? (stf[i-1][1]*5)%MOD : stf[i-1][1]*5); stf[i][2] = (stf[i-1][2]*5 >= MOD ? (stf[i-1][2]*5)%MOD : stf[i-1][2]*5); stf[i][3] = (stf[i-1][3]*5 >= MOD ? (stf[i-1][0]*5)%MOD : stf[i-1][0]*5); } for(int i = 1; i <= N; i++) { scanf("%s", S); int lenS = strlen(S); reverse(S, S+lenS); //hashuj1(S, hsh, lenS); //celi[hsh[lenS-1]]++; hashuj(S, hsh, lenS); reverse(S, S+lenS); ubaci(S, lenS); } int kol = hshidx; DFS(0); for(int q = 0; q < M; q++) { int rez = 0; scanf("%s%s", P, Q); int lenQ = strlen(Q), lenP = strlen(P); reverse(Q, Q+lenQ); hashuj1(Q, hsh, lenQ); key = cudo[hsh[lenQ-1]]; int koji = query(P, lenP); if(key == 0 || koji == -1) { printf("0\n"); return 0; } if(!sorted[key]) { for(int i = 0; i < sz(gde[key]); i++) gde[key][i] = idx[gde[key][i]]; sort(all(gde[key])); sorted[key] = 1; } reverse(P, P+lenP); hashuj1(P, hsh1, lenP); hashuj1(Q, hsh, lenQ); for(int i = 0; i < lenQ; i++) { if(hsh[lenQ-1] - hsh[lenQ-2-i] == hsh1[i]*st[lenQ-i-1]) { lld cur = hsh1[lenP-1]*st[lenQ-i-1] + hsh[lenQ-2-i]; rez += celi[cur]; } } rez += upper_bound(all(gde[key]), idx[koji]+siz[koji]-1) - lower_bound(all(gde[key]), idx[koji]); printf("%d\n", rez); } return 0; }

Compilation message (stderr)

selling_rna.cpp: In function 'void ubaci(char*, int)':
selling_rna.cpp:30:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         int c = f[s[idx]];
                         ^
selling_rna.cpp: In function 'int DFS(int)':
selling_rna.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
selling_rna.cpp: In function 'void hashuj(char*, long long int*, int)':
selling_rna.cpp:56:32: warning: array subscript has type 'char' [-Wchar-subscripts]
         hsh[i] += stf[i][f[s[i]]];
                                ^
selling_rna.cpp: In function 'void hashuj1(char*, long long int*, int)':
selling_rna.cpp:69:32: warning: array subscript has type 'char' [-Wchar-subscripts]
         hsh[i] += stf[i][f[s[i]]];
                                ^
selling_rna.cpp: In function 'int query(char*, int)':
selling_rna.cpp:77:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         int c = f[s[idxx]];
                          ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:110:9: warning: unused variable 'kol' [-Wunused-variable]
     int kol = hshidx;
         ^~~
selling_rna.cpp:84:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
      freopen("02-01.txt", "r", stdin);
      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:85:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
      freopen("out.txt", "w", stdout);
      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:86:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d%d", &N, &M);
               ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", S);
         ~~~~~^~~~~~~~~
selling_rna.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%s", P, Q);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...