제출 #476364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476364		nicolaalexandra	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	718 ms	661828 KiB

selling_rna

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

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40