제출 #395512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395512		KoD	Viruses (BOI20_viruses)	C++17	11 / 100	1 ms	332 KiB

Viruses

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

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

    Vec<Node> node;
    int add_node() {
        node.push_back(Node());
        return (int) node.size() - 1;
    }

    Trie() { add_node(); }

    void insert(const Vec<int>& binary) {
        int pos = 0;
        for (const auto x: binary) {
            if (node[pos].next[x] == -1) {
                node[pos].next[x] = add_node();
            }
            pos = node[pos].next[x];
        }
        node[pos].bad = true;
    }

    void build() {
        std::queue<int> que;
        for (int k = 0; k < 2; ++k) {
            if (node[0].next[k] == -1) {
                node[0].next[k] = add_node();
            }
            node[node[0].next[k]].link = 0;
            que.push(node[0].next[k]);
        }
        while (!que.empty()) {
            const auto u = que.front();
            que.pop();
            for (int k = 0; k < 2; ++k) {
                const auto v = node[u].next[k];
                if (v == -1) {
                    continue;
                }
                int p = node[u].link;
                while (node[p].next[k] == -1) {
                    p = node[p].link;
                }
                node[v].link = node[p].next[k];
                que.push(v);
            }
        }
    }
};

int main() {
    int G, N, M;
    std::cin >> G >> N >> M;
    Vec<Vec<Vec<int>>> graph(G);
    for (int i = 0; i < N; ++i) {
        int a, k;
        std::cin >> a >> k;
        Vec<int> b(k);
        for (auto& x: b) {
            std::cin >> x;
        }
        graph[a].push_back(std::move(b));
    }
    Vec<ll> shortest(G, -1);
    shortest[0] = shortest[1] = 1;
    while (true) {
        bool change = false;
        for (int i = 2; i < G; ++i) {
            for (const auto& v: graph[i]) {
                ll sum = 0;
                for (const auto x: v) {
                    if (shortest[x] == -1) {
                        sum = -1;
                        break;
                    }
                    sum += shortest[x];
                }
                if (sum != -1 and (shortest[i] == -1 or shortest[i] > sum)) {
                    shortest[i] = sum;
                    change = true;
                }
            }
        }
        if (!change) {
            break;
        }
    }
    if (M == 0) {
        for (int i = 2; i < G; ++i) {
            if (shortest[i] == -1) {
                std::cout << "YES\n";
            }
            else {
                std::cout << "NO " << shortest[i] << '\n';
            }
        }
        return 0;
    }
    Trie trie;
    for (int i = 0; i < M; ++i) {
        int k;
        std::cin >> k;
        Vec<int> c(k);
        for (auto& x: c) {
            std::cin >> x;
        }
        trie.insert(c);
    }
    trie.build();
    const auto V = (int) trie.node.size();
    Vec<bool> bad(V);
    for (int i = 0; i < V; ++i) {
        bad[i] = trie.node[i].bad;
    }
    Vec<std::array<int, 2>> to(V);
    for (int i = 0; i < V; ++i) {
        for (int k = 0; k < 2; ++k) {
            int u = i;
            while (trie.node[u].next[k] == -1) {
                u = trie.node[u].link;
            }
            to[i][k] = trie.node[u].next[k];
        }
    }
    if (N == G - 2) {
        Vec<Vec<int>> memo(G, Vec<int>(V, -2));
        auto dfs = [&](auto&& dfs, const int i, const int u) -> int {
            if (memo[i][u] != -2) {
                return memo[i][u];
            }
            if (shortest[i] == -1) {
                return memo[i][u] = -1;
            }
            if (i < 2) {
                return memo[i][u] = (bad[to[u][i]] ? -1 : to[u][i]);
            }
            int v = u;
            assert(graph[i].size() == 1);
            for (const auto x: graph[i][0]) {
                v = dfs(dfs, x, v);
                if (v == -1) {
                    return memo[i][u] = -1;
                }
            }
            return memo[i][u] = v;
        };
        for (int i = 2; i < G; ++i) {
            if (dfs(dfs, i, 0) == -1) {
                std::cout << "YES\n";
            }
            else {
                std::cout << "NO " << shortest[i] << '\n';
            }
        }
        return 0;
    }
    assert(false);
    return 0;
}

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