oj.uz

Submission #1052479

# Submission time Handle Problem Language Result Execution time Memory
1052479 2024-08-10T15:00:45 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 114 ms 200728 KB 
#include <bits/stdc++.h>

using namespace std;

#define task "test"
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define vii vector <ii>
#define vi vector <int>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll

void solve();

int32_t main() {
    if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	cin.tie(0)->sync_with_stdio(0);

    int tc = 1; // cin >> tc;
    FOR(i, 1, tc) {
        solve();
    }
}

const int N = 1e5+5;

int n, m, trch[200], queryAns[N];
pair <string, int> s[N];
vector <ii> query[N];

struct fenwickTree {
    int f[N*20];

    void upd(int id, int val) {
        for(; id<N*20; id+=id&-id) f[id]+=val;
    }

    int get(int id) {
        int res=0;
        for(; id>0; id-=id&-id) res+=f[id];
        return res;
    }

    int getRange(int L, int R) {
        return get(R) - get(L-1);
    }
} fwt;

// build prefix trie

int Time, st[N*20], en[N*20];

struct preNode {
    int cnt = 0, child[4];
    preNode () {
        fill(begin(child), end(child), -1);
    }
};

vector <preNode> preTrie(1);

int pre_add_string(const string &newString) {
    int cur = 0;
    for(char c:newString) {
        int nxtCh = trch[(int)c];
        if(preTrie[cur].child[nxtCh] == -1) {
            preTrie[cur].child[nxtCh] = sz(preTrie);
            preTrie.eb();
        }
        cur = preTrie[cur].child[nxtCh];
    }
    preTrie[cur].cnt++;
    return cur;
}

void pre_trie_dfs(int u) {
    st[u] = ++Time;
    FOR(i, 0, 3) {
        if(preTrie[u].child[i] != -1) {
            pre_trie_dfs(preTrie[u].child[i]);
        }
    }
    en[u] = Time;
}

int pre_get_string(const string &f) {
    int cur = 0;
    for(char c:f) {
        int nxtCh = trch[(int)c];
        if(preTrie[cur].child[nxtCh] == -1) {
            preTrie[cur].child[nxtCh] = sz(preTrie);
            preTrie.eb();
        }
        cur = preTrie[cur].child[nxtCh];
    }
    return cur;
}

// build suffix trie

int sub[N*20], suf_st[N*20], suf_en[N*20], tour[N*20];

struct sufNode {
    int cnt = 0, id = -1, child[4];
    sufNode () {
        fill(begin(child), end(child), -1);
    }
};

vector <sufNode> sufTrie(1);

void suf_add_string(const string &newString, int tour_pos) {
    int cur = 0;
    for(char c:newString) {
        int nxtCh = trch[(int)c];
        if(sufTrie[cur].child[nxtCh] == -1) {
            sufTrie[cur].child[nxtCh] = sz(sufTrie);
            sufTrie.eb();
        }
        cur = sufTrie[cur].child[nxtCh];
    }

    sufTrie[cur].cnt++;
    sufTrie[cur].id = tour_pos;
}

int suf_get_string(const string &f) {
    int cur = 0;
    for(char c:f) {
        int nxtCh = trch[(int)c];
        if(sufTrie[cur].child[nxtCh] == -1) {
            sufTrie[cur].child[nxtCh] = sz(sufTrie);
            sufTrie.eb();
        }
        cur = sufTrie[cur].child[nxtCh];
    }
    return cur;
}

void suf_get_size(int u) {
    suf_st[u] = ++Time;
    tour[Time] = u;
    sub[u] = 1;
    FOR(i, 0, 3) {
        if(sufTrie[u].child[i] != -1) {
            suf_get_size(sufTrie[u].child[i]);
            sub[u] += sub[sufTrie[u].child[i]];
        }
    }
    suf_en[u] = Time;
}

void suf_dfs_ans(int u) {
    int bigCh = -1;
    FOR(i, 0, 3) if(sufTrie[u].child[i] != -1) {
        if(bigCh == -1 || sub[bigCh] < sub[sufTrie[u].child[i]]) {
            bigCh = sufTrie[u].child[i];
        }
    }

    FOR(i, 0, 3) if(sufTrie[u].child[i] != -1 && sufTrie[u].child[i] != bigCh) {
        suf_dfs_ans(sufTrie[u].child[i]);
        FOR(j, suf_st[sufTrie[u].child[i]], suf_en[sufTrie[u].child[i]]) {
            if(sufTrie[tour[j]].id != -1) {
                fwt.upd(sufTrie[tour[j]].id, -sufTrie[tour[j]].cnt);
            }
        }
        /// delete from fenwick tree
    }

    if(bigCh != -1) suf_dfs_ans(bigCh);
    FOR(i, 0, 3) if(sufTrie[u].child[i] != -1 && sufTrie[u].child[i] != bigCh) {
        FOR(j, suf_st[sufTrie[u].child[i]], suf_en[sufTrie[u].child[i]]) {
            if(sufTrie[tour[j]].id != -1) {
                fwt.upd(sufTrie[tour[j]].id, sufTrie[tour[j]].cnt);
            }
        }
        /// add to fenwick tree
    };
//    cout<<u<<" "<<sufTrie[u].id<<" "<<sufTrie[u].cnt<<'\n';
    if(sufTrie[u].id != -1) fwt.upd(sufTrie[u].id, sufTrie[u].cnt);
    /// add u to fenwick tree

    for(auto [preN, id]:query[u]) {
        queryAns[id] = fwt.getRange(st[preN], en[preN]);
//        cout<<st[preN]<<" "<<en[preN]<<" "<<preN<<'\n';
    }
}

void solve() {
    cin >> n >> m;
    trch['C'] = 0, trch['U'] = 1, trch['G'] = 2, trch['A'] = 3;

    FOR(i, 1, n) {
        cin >> s[i].fi;
        s[i].se = pre_add_string(s[i].fi);
    }

    FOR(i, 1, m) {
        string pre, suf; cin >> pre >> suf;
        reverse(all(suf));

        int idp = pre_get_string(pre),
            ids = suf_get_string(suf);

        query[ids].eb(idp, i);
    }

    pre_trie_dfs(0);
    Time = 0;

    FOR(i, 1, n) {
        reverse(all(s[i].fi));
        suf_add_string(s[i].fi, st[s[i].se]);
    }

    suf_get_size(0);
    suf_dfs_ans(0);

    FOR(i, 1, m) {
        cout << queryAns[i] << '\n';
    }
}

Compilation message

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 22360 KB Output is correct
2 Correct 3 ms 22360 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 2 ms 22364 KB Output is correct
5 Correct 2 ms 22364 KB Output is correct
6 Correct 2 ms 22372 KB Output is correct
7 Correct 2 ms 22364 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 200728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23388 KB Output is correct
2 Correct 9 ms 23420 KB Output is correct
3 Correct 12 ms 23644 KB Output is correct
4 Correct 10 ms 23388 KB Output is correct
5 Correct 9 ms 23388 KB Output is correct
6 Correct 11 ms 23512 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 22360 KB Output is correct
2 Correct 3 ms 22360 KB Output is correct
3 Correct 3 ms 22364 KB Output is correct
4 Correct 2 ms 22364 KB Output is correct
5 Correct 2 ms 22364 KB Output is correct
6 Correct 2 ms 22372 KB Output is correct
7 Correct 2 ms 22364 KB Output is correct
8 Runtime error 114 ms 200728 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -