oj.uz

Submission #476368

# Submission time Handle Problem Language Result Execution time Memory
476368 2021-09-26T08:16:07 Z nicolaalexandra Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 642248 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

vector <char> s[DIM];
char p[DIM],q[DIM],w[DIM],a[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];

}

void copiere (char w[], vector<char> v){
    for (int i=0;i<v.size();i++)
        w[i] = v[i];
    w[v.size()] = NULL;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>a;
        lg[i] = strlen(a);

        for (j=0;j<lg[i];j++)
            s[i].push_back(a[j]);

        poz[i] = i;
    }

    sort (poz+1,poz+n+1,cmp);

    for (i=1;i<=n;i++){
        copiere (w,s[poz[i]]);
        add (rad1,w);
    }

    dfs (rad1);


    for (i=1;i<=n;i++){
        reverse (s[poz[i]].begin(),s[poz[i]].end());
        copiere (w,s[poz[i]]);
        add2 (rad2,w);
    }

    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:38:15: warning: NULL used in arithmetic [-Wpointer-arith]
   38 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void add2(trie2*, char*)':
selling_rna.cpp:77:15: warning: NULL used in arithmetic [-Wpointer-arith]
   77 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp: In function 'void query(trie*, char*)':
selling_rna.cpp:88:15: warning: NULL used in arithmetic [-Wpointer-arith]
   88 |     if (*s == NULL)
      |               ^~~~
selling_rna.cpp: In function 'void query2(trie2*, char*)':
selling_rna.cpp:101:15: warning: NULL used in arithmetic [-Wpointer-arith]
  101 |     if (*s == NULL){
      |               ^~~~
selling_rna.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int i=0;i<rad->v.size();i++)
      |                      ~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void copiere(char*, std::vector<char>)':
selling_rna.cpp:129:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i=0;i<v.size();i++)
      |                  ~^~~~~~~~~
selling_rna.cpp:131:19: warning: converting to non-pointer type 'char' from NULL [-Wconversion-null]
  131 |     w[v.size()] = NULL;
      |                   ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 560812 KB Output is correct
2 Correct 638 ms 530956 KB Output is correct
3 Correct 528 ms 473108 KB Output is correct
4 Correct 532 ms 450588 KB Output is correct
5 Correct 677 ms 632788 KB Output is correct
6 Correct 667 ms 642248 KB Output is correct
7 Correct 230 ms 14148 KB Output is correct
8 Correct 732 ms 379796 KB Output is correct
9 Correct 580 ms 319828 KB Output is correct
10 Correct 549 ms 310724 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1596 ms 5960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 600 ms 560812 KB Output is correct
9 Correct 638 ms 530956 KB Output is correct
10 Correct 528 ms 473108 KB Output is correct
11 Correct 532 ms 450588 KB Output is correct
12 Correct 677 ms 632788 KB Output is correct
13 Correct 667 ms 642248 KB Output is correct
14 Correct 230 ms 14148 KB Output is correct
15 Correct 732 ms 379796 KB Output is correct
16 Correct 580 ms 319828 KB Output is correct
17 Correct 549 ms 310724 KB Output is correct
18 Execution timed out 1596 ms 5960 KB Time limit exceeded
19 Halted 0 ms 0 KB -