oj.uz

Submission #332743

# Submission time Handle Problem Language Result Execution time Memory
332743 2020-12-03T06:05:32 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 596 ms 611808 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>

using namespace std;
struct A
{
    int x,y;
    int con=0;
    int nxt[6][6];
}Node[2000005];
int now=1,xx,yy;
char tt[100005];
char tt2[100005];
void New(int here)
{
    Node[here].con=0;
    memset(Node[here].nxt,-1,sizeof(Node[here].nxt));
}
void build(int x,int y,int here)
{
    int a,b;
    Node[here].con++;
    Node[here].x=x;
    Node[here].y=y;

    if(x==xx&&y==xx) return;
    if(x==xx&&y==-1) return;
    if(x==-1&&y==xx) return;

    if(x!=-1)
    {
        if(tt[x]=='A') a=0;
        if(tt[x]=='U') a=1;
        if(tt[x]=='C') a=2;
        if(tt[x]=='G') a=3;
    }
    if(y!=-1)
    {
        if(tt[xx-y-1]=='A') b=0;
        if(tt[xx-y-1]=='U') b=1;
        if(tt[xx-y-1]=='C') b=2;
        if(tt[xx-y-1]=='G') b=3;
    }

    if(x==-1)
    {
        if(Node[here].nxt[5][b]==-1)
        {
            Node[here].nxt[5][b]=now++;
            New(Node[here].nxt[5][b]);
        }
        build(-1,y+1,Node[here].nxt[5][b]);
    }
    else if(y==-1)
    {
        if(Node[here].nxt[a][5]==-1)
        {
            Node[here].nxt[a][5]=now++;
            New(Node[here].nxt[a][5]);
        }
        build(x+1,-1,Node[here].nxt[a][5]);
    }
    else
    {
        if(Node[here].nxt[a][b]==-1)
        {
            Node[here].nxt[a][b]=now++;
            New(Node[here].nxt[a][b]);
        }

        build(x+1,y+1,Node[here].nxt[a][b]);

        if(Node[here].nxt[a][5]==-1)
        {
            Node[here].nxt[a][5]=now++;
            New(Node[here].nxt[a][5]);
        }
        build(x+1,-1,Node[here].nxt[a][5]);

        if(Node[here].nxt[5][b]==-1)
        {
            Node[here].nxt[5][b]=now++;
            New(Node[here].nxt[5][b]);
        }
        build(-1,y+1,Node[here].nxt[5][b]);
    }
}
int Find(int here)
{
    int a,b;
    if((Node[here].x==xx||Node[here].x==-1)&&(Node[here].y==yy||Node[here].y==-1)) return Node[here].con;
    if(Node[here].x==-1||Node[here].x==xx)
    {
        if(tt2[yy-Node[here].y-1]=='A') b=0;
        if(tt2[yy-Node[here].y-1]=='U') b=1;
        if(tt2[yy-Node[here].y-1]=='C') b=2;
        if(tt2[yy-Node[here].y-1]=='G') b=3;

        if(Node[here].nxt[5][b]==-1) return 0;
        return Find(Node[here].nxt[5][b]);
    }

    else if(Node[here].y==-1||Node[here].y==yy)
    {
        if(tt[Node[here].x]=='A') a=0;
        if(tt[Node[here].x]=='U') a=1;
        if(tt[Node[here].x]=='C') a=2;
        if(tt[Node[here].x]=='G') a=3;

        if(Node[here].nxt[a][5]==-1) return 0;
        return Find(Node[here].nxt[a][5]);
    }
    else
    {
        if(tt2[yy-Node[here].y-1]=='A') b=0;
        if(tt2[yy-Node[here].y-1]=='U') b=1;
        if(tt2[yy-Node[here].y-1]=='C') b=2;
        if(tt2[yy-Node[here].y-1]=='G') b=3;

        if(tt[Node[here].x]=='A') a=0;
        if(tt[Node[here].x]=='U') a=1;
        if(tt[Node[here].x]=='C') a=2;
        if(tt[Node[here].x]=='G') a=3;
        if(Node[here].nxt[a][b]==-1) return 0;
        return Find(Node[here].nxt[a][b]);

    }
}
int main()
{
    int N,M,K,t=0,i,j,k,t2,ans;
    scanf("%d %d",&N,&M);

    New(0);
    for(i=0;i<N;i++)
    {
        scanf("%s",tt);
        xx=strlen(tt);
        build(0,0,0);

    }
    while(M--)
    {
        ans=0;
        scanf("%s %s",tt,tt2);
        xx=strlen(tt);
        yy=strlen(tt2);
        printf("%d\n",Find(0));
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:136:13: warning: unused variable 'K' [-Wunused-variable]
  136 |     int N,M,K,t=0,i,j,k,t2,ans;
      |             ^
selling_rna.cpp:136:15: warning: unused variable 't' [-Wunused-variable]
  136 |     int N,M,K,t=0,i,j,k,t2,ans;
      |               ^
selling_rna.cpp:136:21: warning: unused variable 'j' [-Wunused-variable]
  136 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                     ^
selling_rna.cpp:136:23: warning: unused variable 'k' [-Wunused-variable]
  136 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                       ^
selling_rna.cpp:136:25: warning: unused variable 't2' [-Wunused-variable]
  136 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                         ^~
selling_rna.cpp:136:28: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  136 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                            ^~~
selling_rna.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
selling_rna.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |         scanf("%s %s",tt,tt2);
      |         ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void build(int, int, int)':
selling_rna.cpp:52:31: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |         if(Node[here].nxt[5][b]==-1)
      |            ~~~~~~~~~~~~~~~~~~~^
selling_rna.cpp:78:31: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         if(Node[here].nxt[a][5]==-1)
      |            ~~~~~~~~~~~~~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 305644 KB Output is correct
2 Correct 164 ms 305644 KB Output is correct
3 Correct 158 ms 305644 KB Output is correct
4 Correct 157 ms 305644 KB Output is correct
5 Correct 157 ms 305644 KB Output is correct
6 Correct 162 ms 305664 KB Output is correct
7 Correct 156 ms 305664 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 596 ms 611808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 306168 KB Output is correct
2 Correct 182 ms 305772 KB Output is correct
3 Correct 184 ms 305772 KB Output is correct
4 Correct 178 ms 305772 KB Output is correct
5 Correct 187 ms 305772 KB Output is correct
6 Correct 184 ms 305772 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 305644 KB Output is correct
2 Correct 164 ms 305644 KB Output is correct
3 Correct 158 ms 305644 KB Output is correct
4 Correct 157 ms 305644 KB Output is correct
5 Correct 157 ms 305644 KB Output is correct
6 Correct 162 ms 305664 KB Output is correct
7 Correct 156 ms 305664 KB Output is correct
8 Runtime error 596 ms 611808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -