oj.uz

Submission #423037

# Submission time Handle Problem Language Result Execution time Memory
423037 2021-06-10T16:18:49 Z doowey Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 647140 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const int L = (int)2e6 + 100;

unordered_set<int> LEF[L];
unordered_set<int> RIG[L];
int lef[L][4];
int rig[L][4];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    for(int i = 0 ; i < L; i ++ ){
        for(int j = 0 ; j < 4; j ++ ){
            lef[i][j]=-1;
            rig[i][j]=-1;
        }
    }
    int ca = 0, cb = 0;
    int n, m;
    cin >> n >> m;
    string s;
    int cur;
    map<char, int> match;
    match['A'] = 0;
    match['G'] = 1;
    match['C'] = 2;
    match['U'] = 3;
    int id;
    for(int i = 1; i <= n; i ++ ){
        cin >> s;
        cur = 0;
        for(auto x : s){
            id = match[x];
            if(lef[cur][id] == -1){
                ca ++ ;
                lef[cur][id] = ca;
            }
            cur = lef[cur][id];
            LEF[cur].insert(i);
        }
        cur = 0;
        for(int j = s.size() - 1; j >= 0 ; j -- ){
            id = match[s[j]];
            if(rig[cur][id] == -1){
                cb ++ ;
                rig[cur][id] = cb;
            }
            cur = rig[cur][id];
            RIG[cur].insert(i);
        }
    }
    string pi, qi;
    int lli = 0, rri = 0;
    map<pii, int> res;
    int cnt;
    for(int iq = 1; iq <= m ; iq ++ ){
        cin >> pi >> qi;
        reverse(qi.begin(), qi.end());
        lli = rri = 0;
        for(auto x : pi){
            id = match[x];
            if(lef[lli][id] == -1){
                lli = -1;
                break;
            }
            lli = lef[lli][id];
        }
        for(auto x : qi){
            id = match[x];
            if(rig[rri][id] == -1){
                rri = -1;
                break;
            }
            rri = rig[rri][id];
        }
        if(lli == -1 || rri == -1){
            cout << "0\n";
            continue;
        }
        if(res.count(mp(lli, rri))){
            cout << res[mp(lli,rri)] << "\n";
        }
        else{
            cnt = 0;
            if(LEF[lli].size() <= RIG[rri].size()){
                for(auto x : LEF[lli]){
                    if(RIG[rri].count(x)){
                        cnt ++ ;
                    }
                }
            }
            else{
                for(auto x : RIG[rri]){
                    if(LEF[lli].count(x)){
                        cnt ++ ;
                    }
                }
            }
            res[mp(lli,rri)] = cnt;
            cout << cnt << "\n";
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 282116 KB Output is correct
2 Correct 165 ms 282112 KB Output is correct
3 Correct 162 ms 282160 KB Output is correct
4 Correct 163 ms 282052 KB Output is correct
5 Correct 167 ms 282048 KB Output is correct
6 Correct 161 ms 282240 KB Output is correct
7 Correct 162 ms 282148 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 291416 KB Output is correct
2 Correct 254 ms 291280 KB Output is correct
3 Correct 272 ms 291116 KB Output is correct
4 Correct 262 ms 291208 KB Output is correct
5 Correct 272 ms 291296 KB Output is correct
6 Correct 263 ms 291244 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 282116 KB Output is correct
2 Correct 165 ms 282112 KB Output is correct
3 Correct 162 ms 282160 KB Output is correct
4 Correct 163 ms 282052 KB Output is correct
5 Correct 167 ms 282048 KB Output is correct
6 Correct 161 ms 282240 KB Output is correct
7 Correct 162 ms 282148 KB Output is correct
8 Execution timed out 1505 ms 647140 KB Time limit exceeded
9 Halted 0 ms 0 KB -