oj.uz

답안 #933073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933073 2024-02-25T01:04:29 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 1048576 KB 
#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>

using namespace std;

void setio (string name) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }   
}

ll cast (char c) {
    switch (c)
    {
    case 'A':
        return 0;
    case 'C':
        return 1;
    case 'G':
        return 2;
    case 'U':
        return 3;
    }
}

struct Trie {
    struct Node {
        ptr(Node) child[4];
        set<ll> suf;
    };

    ptr(Node) root = ptr(Node) (new Node);

    void add(string& s, ll i) {
        ptr(Node) node = root;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[cast(*it)])
                node->child[cast(*it)] = ptr(Node) (new Node);
            node->child[cast(*it)]->suf.insert(i);
            node = node->child[cast(*it)];
        }
    }

    set<ll> get(string& s) {
        ptr(Node) node = root;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[cast(*it)])
                return {};
            node = node->child[cast(*it)];
        }
        return node->suf;
    }
};

struct RTrie {
    struct Node {
        ptr(Node) child[4];
        set<ll> suf;
    };

    ptr(Node) root = ptr(Node) (new Node);

    void add(string& s, ll i) {
        ptr(Node) node = root;
        for (auto it = s.rbegin(); it != s.rend(); it++) {
            if (!node->child[cast(*it)])
                node->child[cast(*it)] = ptr(Node) (new Node);
            node->child[cast(*it)]->suf.insert(i);
            node = node->child[cast(*it)];
        }
    }

    set<ll> get(string& s) {
        ptr(Node) node = root;
        for (auto it = s.rbegin(); it != s.rend(); it++) {
            if (!node->child[cast(*it)])
                return {};
            node = node->child[cast(*it)];
        }
        return node->suf;
    }
};

struct QTrie {
    struct Node {
        ptr(Node) child[4];
        vector<ll> flag;
    };

    ptr(Node) root = ptr(Node) (new Node);

    void add(string& s, ll i) {
        ptr(Node) node = root;
        for (auto it = s.begin(); it != s.end(); it++) {
            if (!node->child[cast(*it)])
                node->child[cast(*it)] = ptr(Node) (new Node);
            node = node->child[cast(*it)];
        }
        node->flag.push_back(i);
    }
};

struct RQTrie {
    struct Node {
        ptr(Node) child[4];
        vector<ll> flag;
    };

    ptr(Node) root = ptr(Node) (new Node);

    void add(string& s, ll i) {
        ptr(Node) node = root;
        for (auto it = s.rbegin(); it != s.rend(); it++) {
            if (!node->child[cast(*it)])
                node->child[cast(*it)] = ptr(Node) (new Node);
            node = node->child[cast(*it)];
        }
        node->flag.push_back(i);
    }
};

ll n, m;
string s, t;
vector<set<ll>> pre, suf;

void explore(ptr(Trie::Node) snode, ptr(QTrie::Node) qnode) {
    for (ll& i : qnode->flag)
        pre[i] = snode->suf;
    
    range(i, 0, 4) {
        if (snode->child[i] && qnode->child[i])
            explore(snode->child[i], qnode->child[i]);
    }
}

void rexplore(ptr(RTrie::Node) snode, ptr(RQTrie::Node) qnode) {
    for (ll& i : qnode->flag)
        suf[i] = snode->suf;
    
    range(i, 0, 4) {
        if (snode->child[i] && qnode->child[i])
            rexplore(snode->child[i], qnode->child[i]);
    }
}

ll sunion (set<ll>& a, set<ll>& b) {
    ll cnt = 0;
    for (const ll& it : a) {
        if (b.count(it))
            cnt++;
    }
    return cnt;
}

void solve() {
    cin >> n >> m;
    
    Trie tr;
    RTrie rtr;
    range(i, 0, n) {
        cin >> s;
        tr.add(s, i);
        rtr.add(s, i);
    }

    QTrie qtr;
    RQTrie rqtr;
    
    range(i, 0, m) {
        cin >> s >> t;
        qtr.add(s, i);
        rqtr.add(t, i);
    }

    pre.resize(m);
    suf.resize(m);
    explore(tr.root, qtr.root);
    rexplore(rtr.root, rqtr.root);

    range(i, 0, m) 
        cout << sunion(pre[i], suf[i]) << '\n';
}

int main () {
    setio("");
    ll t = 1; 
    // cin >> t;
    while (t--) solve();
}

Compilation message

selling_rna.cpp: In function 'void setio(std::string)':
selling_rna.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'long long int cast(char)':
selling_rna.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1298 ms 601172 KB Output is correct
2 Execution timed out 1517 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 896 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1298 ms 601172 KB Output is correct
9 Execution timed out 1517 ms 1048576 KB Time limit exceeded
10 Halted 0 ms 0 KB -