oj.uz

Submission #289253

# Submission time Handle Problem Language Result Execution time Memory
289253 2020-09-02T13:42:48 Z leductoan Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 393656 KB 
#include<bits/stdc++.h>
using namespace std;
#define task "JOI16_selling_rna"
#define lb lower_bound
#define ub upper_bound
#define ALL(v) (v).begin(),(v).end()
#define zs(v) (int)(v).size()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define cntbit __builtin_popcountll
#define BIT(x, i) (((x) >> (i)) & 1)
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
const ll mod=1000000007; /// 998244353
const int base=311;
const int N=2e6+5;

int cnt1,cnt2,n,q;
string s[100005];
vector<vector<int>> st1, st2, T1, T2;

int conv(char c)
{
    if(c=='A') return 0;
    if(c=='U') return 1;
    if(c=='G') return 2;
    if(c=='C') return 3;
}
void add(vector<vector<int>>&T, int id, string &s, int &cnt, vector<vector<int>> &st)
{
    int root=0;
    for(int i=0;i<zs(s);++i)
    {
        int c=conv(s[i]);
        if(T[root][c]==0) T[root][c]=++cnt;
        root=T[root][c];
        st[root].pb(id);
    }
}
vector<int> get(vector<vector<int>> &T, string &s, vector<vector<int>> &st)
{
    int root=0;
    vector<int> ans={};
    for(int i=0;i<zs(s);++i)
    {
        int c=conv(s[i]);
        if(T[root][c]==0) return ans;
        root=T[root][c];
    }
    return st[root];
}
void biot()
{
    cin>>n>>q;
    int tot=0;
    for(int i=1;i<=n;++i) cin>>s[i], tot+=zs(s[i]);
    st1.resize(tot+4);
    st2.resize(tot+4);
    T1=T2=vector<vector<int>>(tot+5,vector<int>(5));
    for(int i=1;i<=n;++i)
    {
        add(T1,i,s[i],cnt1,st1);
        reverse(ALL(s[i]));
        add(T2,i,s[i],cnt2,st2);
    }
    while(q--)
    {
        string pre,suf;
        cin>>pre>>suf;
        reverse(ALL(suf));
        int ans=0;
        vector<int> tam1=get(T1,pre,st1), tam2=get(T2,suf,st2);
//        for(int i:tam1) cout<<i<<' ';
//        cout<<endl;
        for(int i:tam1) if(binary_search(ALL(tam2),i)) ++ans;
        cout<<ans<<'\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    biot();
}

Compilation message

selling_rna.cpp: In function 'int conv(char)':
selling_rna.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   89 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 393656 KB Output is correct
2 Correct 882 ms 389648 KB Output is correct
3 Correct 714 ms 392380 KB Output is correct
4 Correct 729 ms 388928 KB Output is correct
5 Correct 538 ms 277672 KB Output is correct
6 Correct 450 ms 282188 KB Output is correct
7 Correct 643 ms 259064 KB Output is correct
8 Correct 636 ms 377632 KB Output is correct
9 Correct 614 ms 368504 KB Output is correct
10 Execution timed out 1610 ms 368968 KB Time limit exceeded

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 3 ms 3456 KB Output is correct
3 Correct 2 ms 3584 KB Output is correct
4 Correct 3 ms 3456 KB Output is correct
5 Correct 3 ms 3584 KB Output is correct
6 Correct 3 ms 3456 KB Output is correct
7 Correct 3 ms 3588 KB Output is correct
8 Correct 664 ms 393656 KB Output is correct
9 Correct 882 ms 389648 KB Output is correct
10 Correct 714 ms 392380 KB Output is correct
11 Correct 729 ms 388928 KB Output is correct
12 Correct 538 ms 277672 KB Output is correct
13 Correct 450 ms 282188 KB Output is correct
14 Correct 643 ms 259064 KB Output is correct
15 Correct 636 ms 377632 KB Output is correct
16 Correct 614 ms 368504 KB Output is correct
17 Execution timed out 1610 ms 368968 KB Time limit exceeded