Submission #933064

#	Time	Username	Problem	Language	Result	Execution time	Memory
933064		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1560 ms	251040 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
// sad
map <char, char> mp = {
    { 'A', 'A' },
    { 'U', 'B' },
    { 'C', 'C' },
    { 'G', 'D' },
};

const ll MAXN = 2E5+16;
ll tin[MAXN][2];
ll tout[MAXN][2];
ll n;
vll vans;
ll timer=0;

bool isAnc (ll u, ll v, bool sad) {
    return tin[u][sad] <= tin[v][sad] && tout[v][sad] <= tout[u][sad];
}

/* #define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    vll tree;
    ll n;
    
    SegTree (ll n): tree(2*n), n(n) {}

    void pull (ll l, ll r, ll id) {
        tree[id] = tree[id+1] + tree[id+off];
    }

    void update (ll at, ll val, ll l, ll r, ll id) {
        if (at < l || r < at) return;
        if (l == r) {
            tree[id] += val;
            return;
        }
        update(at, val, l, mid, id+1);
        update(at, val, mid+1, r, id+off);
    }

    void update (ll at, ll val) {
        update(at, val, 0, n-1, 0);
    }

    ll query (ll ql, ll qr, ll l, ll r, ll id) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[id];
        return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
    }

    ll query (ll ql, ll qr) {
        return query(ql, qr, 0, n-1, 0);
    }
} st(2*MAXN); */

struct Trie {
    struct Node {
        ll next[4]{};
        vll ss;
        vll qs;

        Node () {}
    };
    vector <Node> tree;
    ll nodes;

    ll newNode () {
        tree.push_back(Node());
        return nodes++;
    }

    Trie (): nodes(0), tree(0) {
        newNode();
    }

    void add (string str, ll i, bool isQ) {
        ll id=0;
        for (char &c : str) c=mp[c];
        for (char c : str) {
            if (!tree[id].next[c-'A']) tree[id].next[c-'A']=newNode();
            id = tree[id].next[c-'A'];
        }
        (isQ ? tree[id].qs : tree[id].ss).push_back(i);
    }

    /* void dfs_ans (ll id) {
        for (ll i : tree[id].qs) ::tin[i]=::timer++;
        for (ll i : tree[id].ss) ::st.update(::tin[i], -1);
        for (ll i = 0; i < 4; i++) {
            if (!tree[id].next[i]) continue;
            dfs_euler(tree[id].next[i]);
        }
        for (ll i : tree[id].ss) ::st.update(::tin[i], 1);
        for (ll i : tree[id].qs) ::tout[i]=::timer++;
    } */

    void dfs_euler (ll id, bool sad) {
        for (ll i : tree[id].qs) ::tin[i][sad]=::timer++;
        for (ll i : tree[id].ss) ::tin[i][sad]=::timer++;
        for (ll i = 0; i < 4; i++) {
            if (!tree[id].next[i]) continue;
            dfs_euler(tree[id].next[i], sad);
        }
        for (ll i : tree[id].ss) ::tout[i][sad]=::timer++;
        for (ll i : tree[id].qs) ::tout[i][sad]=::timer++; // ideally in the reversed arary, but same thing
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll Q;
    cin >> n >> Q;
    vans.resize(Q, -16);
    Trie norm, rev;
    for (ll i = 0; i < n; i++) {
        string str;
        cin >> str;
        norm.add(str, i, false);
        reverse(str.begin(), str.end());
        rev.add(str, i, false);
    }
    for (ll i = 0; i < Q; i++) {
        string snorm, srev;
        cin >> snorm >> srev;
        reverse(srev.begin(), srev.end());
        norm.add(snorm, i+n, true);
        rev.add(srev, i+n, true);
    }

    norm.dfs_euler(0, false);
    rev.dfs_euler(0, true);
    for (ll i = 0; i < Q; i++) { // sad O(nQ) ;-;
        ll ans=0;
        for (ll j = 0; j < n; j++) {
            if (isAnc(i+n, j, false) && isAnc(i+n, j, true)) ans++;
        }
        cout << ans <<'\n';
    }
        // st.update(tin[i], 1);
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In constructor 'Trie::Trie()':
selling_rna.cpp:70:8: warning: 'Trie::nodes' will be initialized after [-Wreorder]
   70 |     ll nodes;
      |        ^~~~~
selling_rna.cpp:69:19: warning:   'std::vector<Trie::Node> Trie::tree' [-Wreorder]
   69 |     vector <Node> tree;
      |                   ^~~~
selling_rna.cpp:77:5: warning:   when initialized here [-Wreorder]
   77 |     Trie (): nodes(0), tree(0) {
      |     ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40