Submission #625178

#	Time	Username	Problem	Language	Result	Execution time	Memory
625178		KoD	Viruses (BOI20_viruses)	C++17	0 / 100	1090 ms	468 KiB

Viruses

#include <bits/stdc++.h>

using ull = unsigned long long;
using std::vector;
using std::array;
using std::pair;

template <class T>
bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<>>;

class Trie {
    struct Node {
        array<int, 2> next;
        int link;
        bool bad;
        Node() : next({-1, -1}), link(-1), bad(false) {}
    };

    vector<Node> node;

  public:
    Trie() : node({Node()}) {}

    void insert(const vector<int>& str) {
        int u = 0;
        for (const int x : str) {
            if (node[u].next[x] == -1) {
                node[u].next[x] = node.size();
                node.emplace_back();
            }
            u = node[u].next[x];
        }
        node[u].bad = true;
    }

    vector<array<int, 3>> build() {
        std::queue<int> que;
        for (const int k : {0, 1}) {
            if (node[0].next[k] == -1) {
                node[0].next[k] = node.size();
            }
            const int u = node[0].next[k];
            node[u].link = 0;
            que.push(u);
        }
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (const int k : {0, 1}) {
                const int v = node[u].next[k];
                if (v == -1) {
                    continue;
                }
                que.push(v);
                int t = u;
                do {
                    t = node[t].link;
                } while (node[t].next[k] == -1);
                const int s = node[t].next[k];
                node[v].link = s;
                if (node[s].bad) {
                    node[v].bad = true;
                }
            }
        }
        const int V = node.size();
        vector<array<int, 3>> ret(V);
        for (int u = 0; u < V; ++u) {
            for (const int k : {0, 1}) {
                int v = u;
                while (node[v].next[k] == -1) {
                    v = node[v].link;
                }
                ret[u][k] = node[v].next[k];
            }
            ret[u][2] = node[u].bad;
        }
        return ret;
    }
};

struct State {
    ull d;
    int i, j, u, v;
    bool operator<(const State& other) const { return d < other.d; }
    bool operator>(const State& other) const { return d > other.d; }
};

constexpr ull inf = std::numeric_limits<ull>::max();

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int G, N, K;
    std::cin >> G >> N >> K;
    vector<int> id(N);
    vector<vector<int>> seq(N);
    for (int i = 0; i < N; ++i) {
        int k;
        std::cin >> id[i] >> k;
        seq[i].resize(k);
        for (auto& x : seq[i]) {
            std::cin >> x;
        }
    }
    Trie trie;
    while (K--) {
        int k;
        std::cin >> k;
        vector<int> str(k);
        for (auto& x : str) {
            std::cin >> x;
        }
        trie.insert(str);
    }
    const auto data = trie.build();
    const int V = data.size();
    vector complete(G, vector(V, vector(V, inf)));
    vector<vector<vector<vector<ull>>>> make(N);
    for (int i = 0; i < N; ++i) {
        make[i] = vector(seq[i].size() + 1, vector(V, vector(V, inf)));
    }
    min_heap<State> heap;
    const auto push_c = [&](const int i, const int u, const int v, const ull d) {
        if (!data[u][2] and !data[v][2] and setmin(complete[i][u][v], d)) {
            heap.push({d, i, -1, u, v});
        }
    };
    const auto push_m = [&](const int i, const int j, const int u, const int v, const ull d) {
        if (!data[u][2] and !data[v][2] and setmin(make[i][j][u][v], d)) {
            heap.push({d, i, j, u, v});
        }
    };
    for (const int k : {0, 1}) {
        for (int i = 0; i < V; ++i) {
            const int j = data[i][k];
            push_c(k, i, j, 1);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int u = 0; u < V; ++u) {
            push_m(i, 0, u, u, 0);
        }
    }
    while (!heap.empty()) {
        const auto [d, i, j, u, v] = heap.top();
        heap.pop();
        if (j == -1) {
            if (d > complete[i][u][v]) {
                continue;
            }
            for (int k = 0; k < N; ++k) {
                for (int l = 0; l < (int)seq[k].size(); ++l) {
                    if (seq[k][l] == i) {
                        for (int m = 0; m < V; ++m) {
                            if (const ull tmp = make[k][l][m][u]; tmp != inf) {
                                push_m(k, l + 1, m, v, tmp + d);
                            }
                        }
                    }
                }
            }
        } else if (j == (int)seq[i].size()) {
            push_c(id[i], u, v, d);
        } else {
            if (d > make[i][j][u][v]) {
                continue;
            }
            const int k = seq[i][j];
            for (int l = 0; l < V; ++l) {
                if (const ull tmp = complete[k][v][l]; tmp != inf) {
                    push_m(i, j + 1, u, l, d + tmp);
                }
            }
        }
    }
    for (int i = 2; i < G; ++i) {
        ull min = inf;
        for (int u = 0; u < V; ++u) {
            setmin(min, complete[i][0][u]);
        }
        if (min == inf) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO " << min << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18