oj.uz

답안 #933064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933064 2024-02-25T00:37:07 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 251040 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2540 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 166172 KB Output is correct
2 Correct 269 ms 165776 KB Output is correct
3 Correct 223 ms 165548 KB Output is correct
4 Correct 251 ms 166612 KB Output is correct
5 Correct 323 ms 249132 KB Output is correct
6 Correct 332 ms 251040 KB Output is correct
7 Correct 52 ms 3148 KB Output is correct
8 Correct 242 ms 126216 KB Output is correct
9 Correct 226 ms 127700 KB Output is correct
10 Correct 149 ms 127176 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1560 ms 7776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2540 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 212 ms 166172 KB Output is correct
9 Correct 269 ms 165776 KB Output is correct
10 Correct 223 ms 165548 KB Output is correct
11 Correct 251 ms 166612 KB Output is correct
12 Correct 323 ms 249132 KB Output is correct
13 Correct 332 ms 251040 KB Output is correct
14 Correct 52 ms 3148 KB Output is correct
15 Correct 242 ms 126216 KB Output is correct
16 Correct 226 ms 127700 KB Output is correct
17 Correct 149 ms 127176 KB Output is correct
18 Execution timed out 1560 ms 7776 KB Time limit exceeded
19 Halted 0 ms 0 KB -