제출 #1358554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358554		altern23	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	525 ms	461096 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAXN = 1e5;

vector <string> isi[MAXN+5];

string B[MAXN+5];
int ans[MAXN+5];

struct Trie {
    int sum = 0;
    int depth;

    Trie *ch[4] = {NULL};

    void add(string &s, int val) {
        sum += val;
        if (depth == s.size()-1)  return;
        if (ch[s[depth+1]-'A'] == NULL) {
            ch[s[depth+1]-'A'] = new Trie();
            ch[s[depth+1]-'A']->depth = depth+1;
        }
        ch[s[depth+1]-'A']->add(s, val);
    }

    int query(string &s) {
        if (depth == s.size()-1) {
            return sum;
        }
        if (ch[s[depth+1]-'A'] != NULL) {
            return ch[s[depth+1]-'A']->query(s);
        }
        return 0;
    }

    void reset() {
        for (int j = 0; j < 4; j++) ch[j] = NULL;
    }
} tr;

struct Node {
    Node *ch[4] = {NULL};
    int depth, sz = 0, heavy = -1;

    vector <string> isi;
    vector <int> queries;

    void add(string &s, string &b) {
        if (depth == s.size()-1) {
            isi.push_back(b);
            return;
        }
        if (ch[s[depth+1]-'A'] == NULL) {
            ch[s[depth+1]-'A'] = new Node();
            ch[s[depth+1]-'A']->depth = depth+1;
        }
        ch[s[depth+1]-'A']->add(s, b);
    }


    void add_query(string &s, int idx) {
        if (depth == s.size()-1) {
            queries.push_back(idx);
            return;
        }
        if (ch[s[depth+1]-'A'] != NULL) {
            ch[s[depth+1]-'A']->add_query(s, idx);
        }
    }

    void dfs() {
        int MX = 0;
        sz = isi.size();
        for (int j = 0; j < 4; j++) {
            if (ch[j] != NULL) {
                ch[j]->dfs();
                sz += ch[j]->sz;
                if (ch[j]->sz > MX) {
                    MX = ch[j]->sz;
                    heavy = j;
                }
            }
        }
    }

    void compute(bool solve, bool keep) {
        if (solve) {
            for (int j = 0; j < 4; j++) {
                if (j != heavy && ch[j] != NULL) {
                    ch[j]->compute(1, 0);
                }
            }
        }
        if (heavy != -1) ch[heavy]->compute(solve, 1);
        for (int j = 0; j < 4; j++) {
            if (j != heavy && ch[j] != NULL) {
                ch[j]->compute(0, 1);
            }
        }
        for (auto x : isi) {
            tr.add(x, 1);
        }
        if (solve) {
            for (auto x : queries) {
                ans[x] = tr.query(B[x]);
            }
        }
        if (!keep) {            
            tr.reset();
        }
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N, M; cin >> N >> M;

    Node tree;
    tree.depth = -1;

    for (int i = 1; i <= N; i++) {
        string a; cin >> a;
        
        for (auto &j : a) {
            if (j == 'G') j = 'B';
            if (j == 'U') j = 'D';
        }

        string b = a;
        reverse(b.begin(), b.end());

        tree.add(a, b);
    }

    tr.depth = -1;
    
    for (int i = 1; i <= M; i++) {
        string a, b; cin >> a >> b;
        for (auto &j : a) {
            if (j == 'G') j = 'B';
            if (j == 'U') j = 'D';
        }
        for (auto &j : b) {
            if (j == 'G') j = 'B';
            if (j == 'U') j = 'D';
        }

        B[i] = b;
        reverse(B[i].begin(), B[i].end());
        tree.add_query(a, i);
    }
    
    tree.dfs();
    tree.compute(1, 0);

    for (int i = 1; i <= M; i++) cout << ans[i] << "\n";
}

/*
sack
*/

• 서브태스크 1: 10 / 10
• 서브태스크 2: 25 / 25
• 서브태스크 3: 25 / 25
• 서브태스크 4: 40 / 40