이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |