제출 #476364

#제출 시각아이디문제언어결과실행 시간메모리
476364nicolaalexandraSelling RNA Strands (JOI16_selling_rna)C++14
35 / 100
718 ms661828 KiB
#include <bits/stdc++.h> #define DIM 5010 #define INF 2000000000 using namespace std; char s[DIM][DIM],p[DIM],q[DIM],w[DIM]; int poz[DIM],lg[DIM]; int n,m,i,j,l,r,sol; struct trie{ int l,r; trie *f[27]; trie(){ l = INF, r = 0; for (int i=0;i<26;i++) f[i] = 0; } }; trie *rad1 = new trie; struct trie2{ vector <int> v; trie2 *f[27]; trie2(){ for (int i=0;i<26;i++) f[i] = 0; } }; trie2 *rad2 = new trie2; void add (trie *rad, char *s){ if (*s == NULL){ rad->l = min (rad->l,i); rad->r = max (rad->r,i); //rad->l = rad->r = i; } else { if (rad->f[*s-'A'] == 0) rad->f[*s-'A'] = new trie; add (rad->f[*s-'A'],s+1); } } void dfs (trie *rad){ if (rad == NULL) return; for (int i=0;i<26;i++){ if (rad->f[i]){ dfs (rad->f[i]); rad->l = min (rad->l,rad->f[i]->l); rad->r = max (rad->r,rad->f[i]->r); } } } void dfs2 (trie2 *rad){ if (rad == NULL) return; sort (rad->v.begin(),rad->v.end()); for (int i=0;i<26;i++) if (rad->f[i]) dfs2 (rad->f[i]); } void add2 (trie2 *rad, char *s){ rad->v.push_back(i); if (*s == NULL){ return; } else { if (rad->f[*s-'A'] == NULL) rad->f[*s-'A'] = new trie2; add2 (rad->f[*s-'A'],s+1); } } void query (trie *rad, char *s){ if (*s == NULL) l = rad->l, r = rad->r; else { if (rad->f[*s-'A'] == NULL) return; query (rad->f[*s-'A'],s+1); } } void query2 (trie2 *rad, char *s){ if (*s == NULL){ /// cate elemente din vectoru asta sunt intre l si r for (int i=0;i<rad->v.size();i++) if (rad->v[i] >= l && rad->v[i] <= r) sol++; return; } else { if (rad->f[*s-'A'] == NULL) return; query2 (rad->f[*s-'A'],s+1); } } inline int cmp (int a, int b){ for (int i=0;i<min(lg[a],lg[b]);i++) if (s[a][i] != s[b][i]) return s[a][i] < s[b][i]; return lg[a] < lg[b]; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>m; for (i=1;i<=n;i++){ cin>>s[i]; poz[i] = i; lg[i] = strlen (s[i]); } sort (poz+1,poz+n+1,cmp); for (i=1;i<=n;i++) add (rad1,s[poz[i]]); dfs (rad1); for (i=1;i<=n;i++){ reverse (s[poz[i]],s[poz[i]]+lg[poz[i]]); add2 (rad2,s[poz[i]]); } dfs2 (rad2); for (;m--;){ cin>>p>>q; l = r = 0; query(rad1,p); if (!l){ cout<<"0\n"; continue; } reverse (q,q+strlen(q)); sol = 0; query2 (rad2,q); cout<<sol<<"\n"; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void add(trie*, char*)':
selling_rna.cpp:37:15: warning: NULL used in arithmetic [-Wpointer-arith]
   37 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void add2(trie2*, char*)':
selling_rna.cpp:76:15: warning: NULL used in arithmetic [-Wpointer-arith]
   76 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void query(trie*, char*)':
selling_rna.cpp:87:15: warning: NULL used in arithmetic [-Wpointer-arith]
   87 |     if (*s == NULL)
      |               ^~~~
selling_rna.cpp: In function 'void query2(trie2*, char*)':
selling_rna.cpp:100:15: warning: NULL used in arithmetic [-Wpointer-arith]
  100 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for (int i=0;i<rad->v.size();i++)
      |                      ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...