oj.uz

Submission #768337

# Submission time Handle Problem Language Result Execution time Memory
768337 2023-06-27T23:52:08 Z DylanSmith Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 425 ms 365524 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
mt19937 rng;

typedef struct Node {
    int adj[4], par; int freq, pos;
    Node(int p = -1) {
        freq = 0; pos = -1; par = p;
        fill(adj, adj + 4, -1);
    }
} node;

int add(vector<node> &tree, string &s) {
    int cur = 0;
    for (char c : s) {
        if (tree[cur].adj[c - 'a'] == -1) {
            tree[cur].adj[c - 'a'] = sz(tree);
            tree.emplace_back(cur);
        }
        cur = tree[cur].adj[c - 'a'];
    }
    return cur;
}

int find(vector<node> &tree, string &s) {
    int cur = 0;
    for (char c : s) {
        if (tree[cur].adj[c - 'a'] == -1) return -1;
        cur = tree[cur].adj[c - 'a'];
    }
    return cur;
}

string convert(string s) {
    string res = "";
    for (char c : s) {
        if (c == 'A') res += 'a';
        else if (c == 'U') res += 'b';
        else if (c == 'G') res += 'c';
        else res += 'd';
    }
    return res;
}

void merge(vector<node> &tree1, vector<node> &tree2) {
    queue<int> q;
    q.push(0); q.push(0);
    while (!q.empty()) {
        int l = q.front(); q.pop();
        int r = q.front(); q.pop();
        tree1[l].freq += tree2[r].freq;
        for (int k = 0; k < 4; k++) {
            if (tree2[r].adj[k] != -1) {
                if (tree1[l].adj[k] == -1) {
                    tree1[l].adj[k] = sz(tree1);
                    tree1.emplace_back(l);
                }
                q.push(tree1[l].adj[k]);
                q.push(tree2[r].adj[k]);
            }
        }
    }
}

void solve() {
    int N, Q; cin >> N >> Q;
    vector<node> tree(1);
    vector<string> arr(N);
    for (int i = 0; i < N; i++) {
        string s; cin >> s;
        s = convert(s);
        arr[i] = s;
        int j = add(tree, s);
        tree[j].freq++;
        tree[j].pos = i;
    }
    vector<pair<string, string>> queries;
    vector<vector<int>> qMap(sz(tree));
    for (int q = 0; q < Q; q++) {
        string a, b; cin >> a >> b;
        a = convert(a); b = convert(b);
        queries.pb({a, b});
        qMap[find(tree, a)].pb(q);
    }
    vector<vector<node>> suf(sz(tree));
    vector<int> res(Q);
    for (int i = sz(tree) - 1; i > 0; i--) {
        suf[i] = vector<node>(1);
        if (tree[i].freq > 0) {
            string s2 = arr[tree[i].pos];
            reverse(all(s2));
            int j = add(suf[i], s2);
            while (j >= 0) {
                suf[i][j].freq += tree[i].freq;
                j = suf[i][j].par;
            }
        }
        for (int j = 0; j < 4; j++) {
            if (tree[i].adj[j] != -1) {
                if (sz(suf[tree[i].adj[j]]) > sz(suf[i]))
                    swap(suf[i], suf[tree[i].adj[j]]);
            }
        }
        for (int j = 0; j < 4; j++) {
            if (tree[i].adj[j] != -1) {
                merge(suf[i], suf[tree[i].adj[j]]);
            }
        }
        for (int q : qMap[i]) {
            string s2 = queries[q].second;
            reverse(all(s2));
            int j = find(suf[i], s2);
            res[q] = j == -1 ? 0 : suf[i][j].freq;
        }
    }
    for (int i : res) {
        cout << i << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    solve();
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 127176 KB Output is correct
2 Correct 165 ms 138184 KB Output is correct
3 Correct 403 ms 305312 KB Output is correct
4 Correct 396 ms 293700 KB Output is correct
5 Correct 415 ms 352708 KB Output is correct
6 Correct 425 ms 365524 KB Output is correct
7 Correct 104 ms 58440 KB Output is correct
8 Correct 289 ms 249892 KB Output is correct
9 Correct 241 ms 213576 KB Output is correct
10 Correct 219 ms 227924 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6624 KB Output is correct
2 Correct 14 ms 4932 KB Output is correct
3 Correct 18 ms 6328 KB Output is correct
4 Correct 14 ms 5972 KB Output is correct
5 Correct 15 ms 4844 KB Output is correct
6 Correct 18 ms 6316 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 160 ms 127176 KB Output is correct
9 Correct 165 ms 138184 KB Output is correct
10 Correct 403 ms 305312 KB Output is correct
11 Correct 396 ms 293700 KB Output is correct
12 Correct 415 ms 352708 KB Output is correct
13 Correct 425 ms 365524 KB Output is correct
14 Correct 104 ms 58440 KB Output is correct
15 Correct 289 ms 249892 KB Output is correct
16 Correct 241 ms 213576 KB Output is correct
17 Correct 219 ms 227924 KB Output is correct
18 Correct 19 ms 6624 KB Output is correct
19 Correct 14 ms 4932 KB Output is correct
20 Correct 18 ms 6328 KB Output is correct
21 Correct 14 ms 5972 KB Output is correct
22 Correct 15 ms 4844 KB Output is correct
23 Correct 18 ms 6316 KB Output is correct
24 Correct 172 ms 148704 KB Output is correct
25 Correct 181 ms 151408 KB Output is correct
26 Correct 163 ms 146984 KB Output is correct
27 Correct 361 ms 260160 KB Output is correct
28 Correct 123 ms 53624 KB Output is correct
29 Correct 56 ms 14844 KB Output is correct