oj.uz

Submission #476364

# Submission time Handle Problem Language Result Execution time Memory
476364 2021-09-26T08:07:30 Z nicolaalexandra Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 718 ms 661828 KB 
#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;
}

Compilation message

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++)
      |                      ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 568644 KB Output is correct
2 Correct 607 ms 551236 KB Output is correct
3 Correct 532 ms 485844 KB Output is correct
4 Correct 518 ms 471432 KB Output is correct
5 Correct 718 ms 652336 KB Output is correct
6 Correct 707 ms 661828 KB Output is correct
7 Correct 225 ms 23156 KB Output is correct
8 Correct 707 ms 402728 KB Output is correct
9 Correct 609 ms 342708 KB Output is correct
10 Correct 604 ms 331180 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 41292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 572 ms 568644 KB Output is correct
9 Correct 607 ms 551236 KB Output is correct
10 Correct 532 ms 485844 KB Output is correct
11 Correct 518 ms 471432 KB Output is correct
12 Correct 718 ms 652336 KB Output is correct
13 Correct 707 ms 661828 KB Output is correct
14 Correct 225 ms 23156 KB Output is correct
15 Correct 707 ms 402728 KB Output is correct
16 Correct 609 ms 342708 KB Output is correct
17 Correct 604 ms 331180 KB Output is correct
18 Runtime error 36 ms 41292 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -