제출 #332910

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

selling_rna

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40