oj.uz

답안 #332910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332910 2020-12-04T01:23:38 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 379952 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>

using namespace std;
struct A
{
    int nxt[5];
    int con=0;
    int len;
    int l,r;
}Node[5][2000005];

struct B
{
    int l,r;
    int nxl,nxr;
    int nxt;
    int con;
}Node2[20000005];

vector < vector < int > > all[5];
vector < int > xx[5];
pair < int , int > where[100005];
char ttt[100005];
int sz[100005];
int cha[505];
int now[5]={1,1};
int tt[5]={0,0};
int now2=1,N;

int con;
void New(int x,int y,int z)
{
    Node[x][y].con=0;
    Node[x][y].nxt[0]=-1;
    Node[x][y].nxt[1]=-1;
    Node[x][y].nxt[2]=-1;
    Node[x][y].nxt[3]=-1;
    Node[x][y].len=z;
}
void build(int x,int y,int here)
{
    if(Node[x][here].len==sz[y])
    {
        Node[x][here].con++;
        return;
    }
    if(Node[x][here].nxt[all[x][y][Node[x][here].len]]==-1)
    {
        Node[x][here].nxt[all[x][y][Node[x][here].len]]=now[x]++;
        New(x,Node[x][here].nxt[all[x][y][Node[x][here].len]],Node[x][here].len+1);
    }
    build(x,y,Node[x][here].nxt[all[x][y][Node[x][here].len]]);
}
void BFS(int x,int here)
{
    int i;
    Node[x][here].l=tt[x];
    Node[x][here].r=tt[x]+Node[x][here].con-1;
    tt[x]+=Node[x][here].con;
    for(i=0;i<4;i++)
    {
        if(Node[x][here].nxt[i]!=-1)
        {
            BFS(x,Node[x][here].nxt[i]);
            Node[x][here].r=Node[x][Node[x][here].nxt[i]].r;
        }
    }
}
pair < int , int > Find(int x,int here)
{
    if(Node[x][here].len==con) return make_pair(Node[x][here].l,Node[x][here].r);
    if(Node[x][here].nxt[xx[0][Node[x][here].len]]==-1) return make_pair(-1,-1);
    return Find(x,Node[x][here].nxt[xx[0][Node[x][here].len]]);
}

void New2(int l,int r,int nxt,int here)
{
    Node2[here].l=l;
    Node2[here].r=r;
    Node2[here].nxt=nxt;
    Node2[here].nxl=-1;
    Node2[here].nxr=-1;
    Node2[here].con=0;
}
void add(int x,int y,int here)
{
    //printf("%d %d %d %d %d %d\n",x,y,here,Node2[here].l,Node2[here].r,Node2[here].nxt);
    Node2[here].con++;
    if(Node2[here].nxt==-2)
    {
        if(y==Node2[here].l&&y==Node2[here].r) return ;
        if(y<=(Node2[here].l+Node2[here].r)/2)
        {
            if(Node2[here].nxl==-1)
            {
                Node2[here].nxl=now2++;
                New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-2,Node2[here].nxl);
            }
            add(x,y,Node2[here].nxl);
        }
        else
        {
            if(Node2[here].nxr==-1)
            {
                Node2[here].nxr=now2++;
                New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-2,Node2[here].nxr);
            }
            add(x,y,Node2[here].nxr);
        }
    }
    else
    {
        if(Node2[here].nxt==-1)
        {
            Node2[here].nxt=now2++;
            New2(0,N,-2,Node2[here].nxt);
        }
        add(x,y,Node2[here].nxt);
        if(x==Node2[here].l&&x==Node2[here].r) return;
        if(x<=(Node2[here].l+Node2[here].r)/2)
        {
            if(Node2[here].nxl==-1)
            {
                Node2[here].nxl=now2++;
                New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-1,Node2[here].nxl);
            }
            add(x,y,Node2[here].nxl);
        }
        else
        {
            if(Node2[here].nxr==-1)
            {
                Node2[here].nxr=now2++;
                New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-1,Node2[here].nxr);
            }
            add(x,y,Node2[here].nxr);
        }

    }
}

int main()
{

    pair < int , int > a,b;
    int M,K,t=0,i,j,k,t2,ans=0;
    cha['A']=0;
    cha['U']=1;
    cha['C']=2;
    cha['G']=3;
    scanf("%d %d",&N,&M);
    New2(0,N,-1,0);
    New(0,0,0);
    New(1,0,0);
    for(i=0;i<N;i++)
    {
        scanf("%s",ttt);
        sz[i]=strlen(ttt);
        xx[0].clear();
        for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
        xx[1].clear();
        for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
        all[0].push_back(xx[0]);
        all[1].push_back(xx[1]);
        build(0,i,0);
        build(1,i,0);
    }
    BFS(0,0);
    BFS(1,0);
    for(i=0;i<N;i++)
    {
        con=sz[i];
        xx[0]=all[0][i];
        where[i].first=Find(0,0).first;
        xx[0]=all[1][i];
        where[i].second=Find(1,0).first;
        add(where[i].first,where[i].second,0);
    }

    while(M--)
    {
        scanf("%s",ttt);
        xx[0].clear();
        con=strlen(ttt);
        for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
        a=Find(0,0);
        scanf("%s",ttt);
        xx[0].clear();
        con=strlen(ttt);
        for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
        b=Find(1,0);
        if(a.first==-1||b.first==-1) printf("0\n");
        else
        {
            ans=0;
            for(i=0;i<N;i++)
            {
                if(a.first<=where[i].first&&where[i].first<=a.second)
                {
                    if(b.first<=where[i].second&&where[i].second<=b.second) ans++;
                }
            }
            printf("%d\n",ans);
        }

    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:166:55: warning: array subscript has type 'char' [-Wchar-subscripts]
  166 |         for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
      |                                                  ~~~~~^
selling_rna.cpp:168:63: warning: array subscript has type 'char' [-Wchar-subscripts]
  168 |         for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
      |                                                  ~~~~~~~~~~~~~^
selling_rna.cpp:191:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  191 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
      |                                                ~~~~~^
selling_rna.cpp:196:59: warning: array subscript has type 'char' [-Wchar-subscripts]
  196 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
      |                                                ~~~~~~~~~~~^
selling_rna.cpp:152:11: warning: unused variable 'K' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |           ^
selling_rna.cpp:152:13: warning: unused variable 't' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |             ^
selling_rna.cpp:152:21: warning: unused variable 'k' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                     ^
selling_rna.cpp:152:23: warning: unused variable 't2' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                       ^~
selling_rna.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  188 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  193 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 352748 KB Output is correct
2 Correct 171 ms 352748 KB Output is correct
3 Correct 170 ms 352748 KB Output is correct
4 Correct 172 ms 352776 KB Output is correct
5 Correct 173 ms 352748 KB Output is correct
6 Correct 173 ms 352620 KB Output is correct
7 Correct 171 ms 352620 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 401 ms 372744 KB Output is correct
2 Correct 509 ms 379372 KB Output is correct
3 Correct 448 ms 375404 KB Output is correct
4 Correct 498 ms 379244 KB Output is correct
5 Correct 481 ms 375148 KB Output is correct
6 Correct 475 ms 375348 KB Output is correct
7 Correct 326 ms 366700 KB Output is correct
8 Correct 507 ms 379952 KB Output is correct
9 Correct 489 ms 378604 KB Output is correct
10 Correct 392 ms 377068 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1566 ms 359380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 352748 KB Output is correct
2 Correct 171 ms 352748 KB Output is correct
3 Correct 170 ms 352748 KB Output is correct
4 Correct 172 ms 352776 KB Output is correct
5 Correct 173 ms 352748 KB Output is correct
6 Correct 173 ms 352620 KB Output is correct
7 Correct 171 ms 352620 KB Output is correct
8 Correct 401 ms 372744 KB Output is correct
9 Correct 509 ms 379372 KB Output is correct
10 Correct 448 ms 375404 KB Output is correct
11 Correct 498 ms 379244 KB Output is correct
12 Correct 481 ms 375148 KB Output is correct
13 Correct 475 ms 375348 KB Output is correct
14 Correct 326 ms 366700 KB Output is correct
15 Correct 507 ms 379952 KB Output is correct
16 Correct 489 ms 378604 KB Output is correct
17 Correct 392 ms 377068 KB Output is correct
18 Execution timed out 1566 ms 359380 KB Time limit exceeded
19 Halted 0 ms 0 KB -