oj.uz

Submission #1025014

# Submission time Handle Problem Language Result Execution time Memory
1025014 2024-07-16T14:17:04 Z _8_8_ Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 621396 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 2e6 + 20, MOD = (int)1e9+7;
 
struct node{
    node *next[26];
    int tin,tout;
    vector<int> id;
    node(){
        tin = 0,tout = 0;
        for(int i = 0;i < 26;i++){
            next[i] = nullptr;
        }
    }
};

node *p = new node(),*s = new node();
using pnode = node *;
int sp = 0,ss = 0;
int n,q;
void add(pnode v,string &x,int j){
    for(int i = 0;i < (int)x.size();i++){
        if(!v->next[(x[i] - 'A')]){
            v->next[(x[i] - 'A')] = new node();
        }
        v = v->next[(x[i] - 'A')];
    }
    v->id.push_back(j);
}
int timer = 0;
array<int,2> pt[N];
void dfs(pnode v){
    v->tin = ++timer;
    for(int k:v->id){
        if(pt[k][0] == -1){
            pt[k][0] = timer;
        }else{
            pt[k][1] = timer;
        }
    }
    for(int t = 0;t < 26;t++){
        if(v->next[t]){
            dfs(v->next[t]);
        }
    }
    v->tout = ++timer;
}
pair<int,int> get_tin(pnode v,string &x){
    for(int i = 0;i < (int)x.size();i++){
        if(v->next[(x[i] - 'A')]){
            v = v->next[(x[i] - 'A')];
        }else return {-1,-1};
    }
    return {v->tin,v->tout};
}
void test(){
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        string t;
        cin >> t;
        add(p,t,i);
        reverse(t.begin(),t.end());
        add(s,t,i);
        pt[i] = {-1,-1};
    }
    dfs(p);
    timer = 0;
    dfs(s);
    for(int i = 0;i < q;i++){
        string x,y;
        cin >> x >> y;
        reverse(y.begin(),y.end());
        pair<int,int> ti = get_tin(p,x),to = get_tin(s,y);
        // cout << ti.first << ' ' <<ti.second << ' ' << to.first << ' ' <<to.second << '\n';
        if(ti.first == 0 || to.first == 0){
            cout << 0 << '\n';continue;
        }
        int c = 0;
        for(int j = 1;j <= n;j++){
            if(pt[j][0] >= ti.first && pt[j][0] <= ti.second && pt[j][1] >=to.first && pt[j][1] <= to.second){
                c++;
            }
        }
        cout << c << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 498228 KB Output is correct
2 Correct 423 ms 471868 KB Output is correct
3 Correct 398 ms 491092 KB Output is correct
4 Correct 427 ms 467508 KB Output is correct
5 Correct 546 ms 612432 KB Output is correct
6 Correct 554 ms 621396 KB Output is correct
7 Correct 42 ms 6736 KB Output is correct
8 Correct 378 ms 364372 KB Output is correct
9 Correct 346 ms 306000 KB Output is correct
10 Correct 267 ms 295000 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 397 ms 498228 KB Output is correct
9 Correct 423 ms 471868 KB Output is correct
10 Correct 398 ms 491092 KB Output is correct
11 Correct 427 ms 467508 KB Output is correct
12 Correct 546 ms 612432 KB Output is correct
13 Correct 554 ms 621396 KB Output is correct
14 Correct 42 ms 6736 KB Output is correct
15 Correct 378 ms 364372 KB Output is correct
16 Correct 346 ms 306000 KB Output is correct
17 Correct 267 ms 295000 KB Output is correct
18 Execution timed out 1538 ms 1624 KB Time limit exceeded
19 Halted 0 ms 0 KB -